The language A $=$ L$($G$)$ is defined as the set of strings where each string in A is of the form

abkaEabka for any k $>=0,$ where E is an arithmetic expression over floating$-$point numbers, as

defined by the set of production rules of the corresponding Context free grammar. Consider the

following context free grammar G for the language A:

G $=($VN$,$ VT$,$ P$,$ S$),$

where,

VN $=\{$S$,$ T$,$ C$,$ H$,$ Y$,$ N$\}$ is the set of non$-$terminals $($variables$)$;

VT $=\{.,0,1,2,...,9,+,-,*,/,(,),$ a$,$ b $\},$ the set of terminal symbols

$(1)$

which includes a dot for float$-$point numbers;

the starting variable is S; and

P: the set of production rules are

S $->$ aT a

T $->$ bT b $|$ aCa

C $->$ C$+$C $|$ C$-$C $|$ C$*$C $|$ C$/$C $|($C$)|$ H

H $->$ Y$.$Y $|$ Y$.|.$Y

Y $->$ NY $|$ N

N $->0|1|2||9$

Let us consider the string w$=$abbba$(15.-(6\mathrm{.}312*\mathrm{.}7))$abbba$$ and check whether this string

can be generated by the above CFG or not.

This, we can show by using the derivation with G as follows:

S

$$ aT a

$$ abT ba

$$ abbT bba

$$ abbbT bbba

$$ abbbaCabba

$$ abbba$($C$)$abbba

$$ abbba$($C$-$C$)$abbba

$$ abbba$($C$-($C$))$abbba

$$ abbba$($C$-($C$*$C$))$abbba

$$ abbba$($H$-($C$*$C$))$abbba

$$ abbba$($Y $.-($C$*$C$))$abbba

$$ abbba$($NY $.-($C$*$C$))$abbba

$$ abbba$($NN $.-($C$*$C$))$abbba

$$ abbba$(1$N $.-($C$*$C$))$abbba

$$ abbba$(15.-($C$*$C$))$abbba

$$ abbba$(15.-($H$*$C$))$abbba

$$ abbba$(15.-($Y $.$Y $*$C$))$abbba

$$ abbba$(15.-($N $.$Y $*$C$))$abbba

$$ abbba$(15.-(6.$Y $*$C$))$abbba

$$ abbba$(15.-(6.$NY $*$C$))$abbba

$$ abbba$(15.-(6.$NNY $*$C$))$abbba

$$ abbba$(15.-(6.$NNN $*$C$))$abbba

$$ abbba$(15.-(6\mathrm{.}3$NN $*$C$))$abbba

$$ abbba$(15.-(6\mathrm{.}31$N $*$C$))$abbba

$$ abbba$(15.-(6\mathrm{.}312*$C$))$abbba

$$ abbba$(15.-(6\mathrm{.}312*$H$))$abbba

$$ abbba$(15.-(6\mathrm{.}312*.$Y $))$abbba

$$ abbba$(15.-(6\mathrm{.}312*.$N $))$abbba

$$ abbba$(15.-(6\mathrm{.}312*\mathrm{.}7))$abbba

$3$ PDA for A

First you are to construct a PDA M $=($Q$,\backslash$Sigma $,\backslash$Gamma $,\backslash$delta $,$ q$0,$ Z$0,$F $)$ that recognizes A$,$ where $\backslash$Sigma is

defined in equation $(1).$

In this project, the machine you design needs to only recognize the language A$,$ not to

evaluate the arithmetic expression