Language Recognition with a PDA(Pushdown Automaton)

Author: Andrew Gyakobo

Introduction

The following project should define a PDA that in its turn would recognize a specific context-free language.

Let's have a look at Language A

A, in simple terms, is a language that defines all necessary arithmetic floating point numbers and valid operations on said decimal or whole numbers.
A select string of language A is of the form: $ab^kaEab^ka, k>=0$
Here is an example string: $abba(1.2*(1.-2.+3.1))abba$

Note

Language A is not a regular language, however, it's a context-free language

Context Free Grammar for A

Language A can be defined by a 4-tuple context-free grammar $G = (V, \Sigma, R, S)$, where:

V = {S, T, C, H, Y, N} (set of variables, or non-terminals)
$\Sigma$ = {., 0, 1, 2, ..., 9, +, -, *, /, (, ), a, b} (Mind you $\Sigma$ is the alphabet of all available letters, digits, and characters)
S (start variable)

Speaking about R, the rules are as follows:

$S \rightarrow aTa$
$T \rightarrow bTb|aCa$
$C \rightarrow C+C|C-C|C*C|C/C|(C)|H$
$H \rightarrow Y.Y|Y.|.Y$
$Y \rightarrow NY|N$
$N \rightarrow 0|1|2|3|4|5|6|7|8|9$

Let's now handle a sample example

$S \Rightarrow aTa \Rightarrow abTba \Rightarrow abbTbba \Rightarrow abba(C)abba \Rightarrow abba(C * C)abba$

$\Rightarrow abba(C* (C))abba \Rightarrow abba(C * (C-C+C))abba$

$\Rightarrow abba(H * (C-C+C))abba \Rightarrow abba(Y.Y * (C-C+C))abba \Rightarrow abba(N.N * (C-C+C))abba$

$\Rightarrow abba(1.2*(C-C+C))abba \Rightarrow abba(1.2*(H-C+C))abba \Rightarrow abba(1.2 * (Y.-C+C))abba$

$\Rightarrow abba(1.2*(N.-C+C))abba \Rightarrow abba(1.2*(1.-C+C))abba \Rightarrow abba(1.2 * (1. - H + C))abba$

$\Rightarrow abba(1.2 * (1. - Y. + C))abba \Rightarrow abba(1.2 * (1. - N. + C))abba \Rightarrow abba(1.2 * (1. - 2. + C))$

$\Rightarrow abba(1.2 * (1. - 2. + H))abba \Rightarrow abba(1.2 * (1. - 2. + Y.Y))abba \Rightarrow abba(1.2 * (1. - 2. + 3.1))abba$

Pushdown Automaton 'M'

Here's a simple graphic demonstration of the PDA:

Examples

Let's run the Pushdown Automaton M on the following string: