How do I convert this PDA to CFG? PDA to CFG

I am currently stuck with this, any help would be appreciated, thank you in advance!

  • 2
    $\begingroup$ Does this answer your question? How to convert PDA to CFG $\endgroup$ – ttnick Apr 20 '20 at 10:22
  • $\begingroup$ As you may have seen already, the language of this PDA is $L = \{a^n b^m \mid n \geq m\}$ (assuming the PDA accepts a string if the stack is empty). If you are not interested in the algorithm, you might want to construct the grammar from this description which should be fairly easy. $\endgroup$ – ttnick Apr 20 '20 at 10:25

From the PDA diagram we get the transition function as follows:

  1. $\delta(q,a,Z_0)=(q,ZZ_0)$

  2. $\delta(q,a,Z)=(q,ZZ)$

  3. $\delta(q,\epsilon,Z)=(r,Z)$

  4. $\delta(r,b,Z)=(r,\epsilon)$

  5. $\delta(r,\epsilon,Z)=(p,\epsilon)$

  6. $\delta(p,\epsilon,Z)=(p,\epsilon)$

  7. $\delta(p,\epsilon,Z_0)=(p,\epsilon)$

Now let $G$ be the context free grammar and V be the set of variables. Now we represent a variable depending on the state $p$ which the PDA was in before having the ultimate effect of popping an element $X$ from the stack and ultimately landing in the state $q$, as $[pXq]$ where $p$,$q$ are any arbitrary states in the PDA and $X$ is any arbitrary stack symbol.

So our variables will be of the form $[\{p,q,r\} \times \{Z,Z_0\} \times \{p,q,r\}]$

So corresponding to the transition 1 we have the following productions:

1.$[qZ_0q] \rightarrow a[qZq][qZ_0q]$

2.$[qZ_0q] \rightarrow a[qZr][rZ_0q]$

3.$[qZ_0q] \rightarrow a[qZp][pZ_0q]$

4.$[qZ_0p] \rightarrow a[qZq][qZ_0p]$

5.$[qZ_0p] \rightarrow a[qZp][pZ_0p]$

6.$[qZ_0p] \rightarrow a[qZr][rZ_0p]$

7.$[qZ_0r] \rightarrow a[qZq][qZ_0r]$

8.$[qZ_0r] \rightarrow a[qZp][pZ_0r]$

9.$[qZ_0r] \rightarrow a[qZr][rZ_0r]$

From transition 2 we have:

10.$[qZq] \rightarrow a[qZq][qZq]$

11.$[qZq] \rightarrow a[qZp][pZq]$

12.$[qZq] \rightarrow a[qZr][rZq]$

13.$[qZp] \rightarrow a[qZq][qZp]$

14.$[qZp] \rightarrow a[qZp][pZp]$

15.$[qZp] \rightarrow a[qZr][rZp]$

16.$[qZr] \rightarrow a[qZq][qZr]$

17.$[qZr] \rightarrow a[qZp][pZr]$

18.$[qZr] \rightarrow a[qZr][rZr]$

From transition $3$ we have:

19.$[qZq] \rightarrow [rZq]$

20.$[qZp] \rightarrow [rZp]$

21.$[qZr] \rightarrow [rZr]$

from transition $4$ we have:

22.$[rZr] \rightarrow b$

from transition $5$ we have:

23.$[rZp] \rightarrow \epsilon$

From transition $6$ we have:

24.$[pZp] \rightarrow \epsilon$

From transition $7$ we have:

25.$[pZ_0p] \rightarrow \epsilon$

Now let us rename our variables which occur on the $LHS$ of the productions using simpler names as:

$[qZ_0q] = A$, $[qZ_0p] = B$,$[qZ_0r] = C$,$[qZq] = D$,$[qZp] = E$,$[qZr] = F$, $[rZr] = G$,$[rZp] = H$,$[pZp] = I$,$[pZ_0p] = J$

Now we rewrite the productions with the new variable names substituted but we omit those productions whose body has a variable of the form $[pXq]$ which cannot be expanded so, for this reason productions $2,3,6,8,9,11,12,17,19$ are discarded.

So we have:

$A \rightarrow aDA$

$B \rightarrow aDB | aEJ$

$C \rightarrow aDC$

$D \rightarrow aDD$

$E \rightarrow aDE | aEI | aFH | H$

$F \rightarrow aDF | aFG | G$

$G \rightarrow b$

$H \rightarrow \epsilon$

$I \rightarrow \epsilon$

$J \rightarrow \epsilon$

Now let $S$ be the start symbol and we add productions:

$S \rightarrow A | B | C $

So the resulting CFG $G'$ is

$G' = (\{S,A,B,C,D,E,F,G,H,I,J\},\{a,b\},P,S)$ where $P$ contained the productions described above.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.