Example $7\mathrm{.}6$

Construct a PDA that accepts the language

generated by a grammar with productions

$S$aSbb$|a.$

Solution:

Transform the grammar into Greibach normal

form as follows:

$S$aSA$|a,$

$AbB,$

$Bb.$

The corresponding automaton $M$ has three states

$\{q_0,q_1,q_2\}$ where $q_0$ is initial state and $q_2$ is final state. Example $7\mathrm{.}6($Con$\text{'}$t$)$

Solution: $($Con$\text{'}$t$)$

First, put the start symbol $S$ on the stack by

$(q_0,,z)=\{(q_1,Sz)\}.$

The production $S$aSA will be simulated in the PDA

by removing $S$ from the stack and

replacing it with $SA,$

while reading a from the input.

Similarly, $S$a should cause the PDA to read

an a while simply removing $S.$

Thus, these two productions are represented in $M$ :

$(q_1,a,S)=\{(q_1,SA),(q_1,)\}.$

In the similar way, the other productions give:

$(q_1,b,A)=\{(q_1,B)\},$

$(q_1,b,B)=\{(q_1,)\},$

$(q_1,,z)=\{(q_2,z)\}.$Prove that the pda in Example $7\mathrm{.}6$ accepts the language $L=\{a^{n+1}{b}^{2n}$:$n0\}.[10$ pts$]$