= Solution
Use the standard <conversion of a context-free grammar to a pushdown automaton>, implementing a <leftmost derivation> on a <stack>. Take control states $q_s,q,q_f$, input <alphabet> $\{a,b\}$, <stack alphabet> $\{S,T,U,a,b,\bot\}$, initial control state $q_s$, initial <stack> symbol $\bot$, and sole final control state $q_f$. The symbol $\bot$ is a fresh <stack bottom marker>. As in part (a), the top of the <stack> is written on the left.
Initialize with
$$
\delta(q_s,\varepsilon,\bot)=\{(q,S\bot)\}.
$$
In control state $q$, replace a top <nonterminal symbol> by one of its <production rule> right-hand sides:
$$
\begin{aligned}
\delta(q,\varepsilon,S)&=\{(q,UST),(q,ST),(q,\varepsilon)\},\\
\delta(q,\varepsilon,U)&=\{(q,a),(q,aT)\},\\
\delta(q,\varepsilon,T)&=\{(q,b)\}.
\end{aligned}
$$
The replacements are written in the order in which they are to be processed. For example, replacing $S$ by $UST$ leaves $U$ on top; an implementation using individual push operations pushes $T$, then $S$, then $U$.
Match and pop top <terminal symbols> by
$$
\delta(q,a,a)=\{(q,\varepsilon)\},\qquad
\delta(q,b,b)=\{(q,\varepsilon)\}.
$$
Finally include
$$
\delta(q,\varepsilon,\bot)=\{(q_f,\bot)\}.
$$
All unlisted transitions have no choices; $q_f$ has no outgoing transitions. This is <acceptance by final state>, leaving the bottom marker on the <stack>. Taking the last transition too early cannot cause false acceptance, because an unread input suffix remains and $q_f$ cannot consume it.
For correctness, after initialization the <stack> contains the unprocessed part of a sentential form. Expanding a top <nonterminal symbol> simulates one step of a <leftmost derivation>, and popping a matching <terminal symbol> transfers it to the already-read input prefix. Thus if the input prefix consumed so far is $u$ and the <stack> above $\bot$ is $\alpha$, then $S\Rightarrow_G^*u\alpha$. Acceptance gives $S\Rightarrow_G^*w$ for the entire input $w$.
Conversely, any <leftmost derivation> of $w$ specifies choices of these transitions: expand the next <nonterminal symbol>, and read each resulting leading <terminal symbol> when it reaches the top. After all symbols of $w$ are consumed, only $\bot$ remains, enabling the move to $q_f$. \b[The <nondeterministic pushdown automaton> therefore recognizes exactly $L(G)$.] The <empty word> is accepted by choosing $S\to\varepsilon$ after initialization.
$$
\boxed{L(M)=L(G),\qquad F=\{q_f\}.}
$$
Back to article page
