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.)

Thanks in advance.

  • 1
    $\begingroup$ 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. $\endgroup$ Aug 18, 2022 at 15:59
  • $\begingroup$ @HendrikJan working on finding them. Thanks for the edit btw. $\endgroup$
    – Uduru
    Aug 18, 2022 at 16:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.