[Solved]: How to convert PDA to CFG

Problem Detail: 

I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG?

For example: to write CFG for the automata

My attempt:

$S=A_{03}$ because $q_{\color{blue}0}$ is the initial state and $q_{\color{blue}3}$ is the final state.

There are $4$ states so we will have $4^2$ variables:

$$A_{00},A_{01},A_{02},A_{03},\\ A_{10},A_{11},A_{12},A_{13},\\ A_{20},A_{21},A_{22},A_{23},\\ A_{30},A_{31},A_{32},A_{33}$$

for each state $q_{i}$ of the automata $A_{ii}\to\varepsilon$

$$A_{00}\to \varepsilon\\ A_{11}\to \varepsilon\\ A_{22}\to \varepsilon\\ A_{33}\to \varepsilon\\$$

For each triplet of states $q_i,q_j,q_k$, we add the rule $A_{ij}\to A_{ik}A_{jk}$, this gives us $4^3=64$ rules:

$$A_{00}\to A_{00}A_{00}|A_{01}A_{10}|A_{02}A_{20}|A_{03}A_{30}\\ A_{01}\to A_{00}A_{01}|A_{01}A_{11}|A_{02}A_{21}|A_{03}A_{31}\\ A_{02}\to A_{00}A_{02}|A_{01}A_{12}|A_{02}A_{22}|A_{03}A_{32}\\ \bullet\\ \bullet\\ \bullet\\ A_{33}\to A_{30}A_{03}|A_{31}A_{13}|A_{32}A_{23}|A_{33}A_{33}\\$$

I am stuck here

Asked By : Nehorai

Answered By : vonbrand

There is a standard construction to do this, discussed in all formal languages/automata courses. It results in gigantic grammars, often with lots of useless productions and nonterminals.

Added, as requested by Nehorai:

Take a PDA $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \varnothing)$ that accepts $L = \mathcal{N}(M)$ by empty stack (if you have a PDA accepting by final state, first convert to empty stack). We define a CFG that accepts $L$. The nonterminals are symbols of the form $[p, A, q]$ with $p, q \in Q$, $A \in \Gamma$, and a start symbol $S$. The idea is that if $[p, A, q] \Rightarrow^* \sigma$, then if $M$ starts in state $p$ with $A$ on its stack, after consuming $\sigma$ it might be in state $q$ and the stack is shorter by one symbol for the first time. Consider an $A$ on the (eventually empty) stack as commitment to get rid of it.

If there is a move $(p, A_1 A_2 \dots A_n) \in \delta(q, x, A)$ with $x = \epsilon$ or $x \in \Sigma$, this adds productions:

$\begin{align} [q, A, q_n] \rightarrow x [p A_1 q_1] [q_1 A_2 q_2] \dots [q_{n - 1} A_n q_n] \end{align}$

I.e., we consume $x$ from the input (generate it in the grammar), going to state $p$, from which we now are committed to get rid of $A_1 \dots A_N$. We don't know what states $q_1, \dotsc, q_n$ are involved, we just know that after consuming e.g. $A_i$ we will be in some state $q_i$, from which we have to consume $A_{i + 1}$. So we will have to consider all possible collections of states for them.

In the special case $(p, \epsilon) \in \delta(q, x, A)$, the above simplifies to:

$\begin{align} [q, A, p] \rightarrow x \end{align}$

If $x = \epsilon$, the above formally doesn't give a context free grammar, but with the standard construction $\epsilon$ productions can be eliminated.

To start the ball rolling, the stack initially contains just $Z_0$, we are in state $q_0$, and end up in any state:

$\begin{align} S \rightarrow [q_0, Z_0, q] \end{align}$

for any state $q \in Q$.

This should convince you the above construction is correct. It is far from a proof...

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51658