# How do I convert this PDA to CFG?

How do I convert this PDA to CFG?

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

• Does this answer your question? How to convert PDA to CFG – ttnick Apr 20 '20 at 10:22
• 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. – 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.