0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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$
    – Hendrik Jan
    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

0

Reset to default

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.