Non-deterministic Pushdown Automaton to Context-Free Grammar

While doing the exercise about questions about transforming NPDA to CFG, I encountered the following question:

Find a CFG for the following NPDA $$M = (\{q_0, q_1\}, \{a, b\}, \{A, z\}, \delta, q_0, z, \{q_1\})$$, with transitions: \begin{align} \delta(q_0, a, z) &= \{(q_0, Az)\} \\ \delta(q_0, b, A) &= \{(q_0, AA)\} \\ \delta(q_0, a, A) &= \{(q_1, \lambda)\} \end{align}

Since all the transitions are in the form $$\delta(q_i, a, A) = \{c_1, c_2, \ldots, c_n\}$$ where $$c_i = (q_j, \lambda)\mid(q_j, BC)$$, I tried the procedure taught in the book I was reading:

• For the transition reducing the height of the stack, we get $$(q_0Aq_1) \rightarrow a$$
• Then for the other two transitions, we get \begin{align} (q_0zq_0) &\rightarrow a(q_0Aq_0)(q_0zq_0) \mid a(q_0Aq_1)(q_1zq_0) \\[1ex] (q_0zq_1) &\rightarrow a(q_0Aq_0)(q_0zq_1) \mid a(q_0Aq_1)(q_1zq_1) \\[1ex] (q_0Aq_0) &\rightarrow b(q_0Aq_0)(q_0Aq_0) \mid b(q_0Aq_1)(q_1Aq_0) \\[1ex] (q_0Aq_1) &\rightarrow b(q_0Aq_0)(q_0Aq_1) \mid b(q_0Aq_1)(q_1Aq_1) \end{align}

Since there are no productions of $$q_1\alpha q_k$$ at the left size, we eliminate every productions with them, resulting in \begin{align} (q_0zq_0) &\rightarrow a(q_0Aq_0)(q_0zq_0) \\[1ex] (q_0zq_1) &\rightarrow a(q_0Aq_0)(q_0zq_1) \\[1ex] (q_0Aq_0) &\rightarrow b(q_0Aq_0)(q_0Aq_0) \\[1ex] (q_0Aq_1) &\rightarrow b(q_0Aq_0)(q_0Aq_1) \end{align} And the starting symbol being $$(q_0zq_1)$$.

But from here, if we replace $$(q_0zq_1)$$ with $$S$$, $$(q_0Aq_0)$$ with $$A$$, $$(q_0zq_0)$$ with $$B$$ and $$(q_0Aq_1)$$ with $$C$$, its easy to spot that it never terminates: \begin{align} B &\rightarrow aAB \\[1ex] S &\rightarrow aAS \\[1ex] A &\rightarrow bAA \\[1ex] C &\rightarrow a\mid bAC \end{align}

So the questuion is: What am I doing wrong? (If this does help — From the Peter Linz book, 6th-edition, Section 7.2 Exercise 16.)

• You seem to be doing right. The original PDA can only push symbols except it can pop one $A$ while moving to state $q_1$. Probably a typo. I cannot find errata. Commented Aug 18, 2022 at 15:59