How to convert PDA to CFG

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

• csee.umbc.edu/~chang/cs451.f08/pda2cfg.pdf – 3SAT Jan 9 '16 at 16:11
• Where have you looked? Have you consulted standard textbooks? We expect you to do research/self-study in the standard resources before asking here, and to show us in the question what research/self-study you've done. This construction is documented in standard automata theory textbooks -- if yours doesn't explain it, you need a new textbook. – D.W. Jan 9 '16 at 22:07
• Why are you stuck? What prevents you from following the algorithm further? – Raphael Aug 30 '16 at 8:59
• Looks like you missed two productions, corresponding to the push/pop of Z and of X. Go back and look at the algorithm. – Rick Decker Dec 11 '17 at 14:49

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.

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

• This does not seem to fit the Sipser style automaton given in the drawing where we have transitions like $(q,X) \in \delta(q,a,\varepsilon)$. – Hendrik Jan Jan 10 '16 at 22:03
• @HendrikJan, those transitions aren't allowed in a PDA – vonbrand Jan 10 '16 at 22:10
• Indeed, they are not allowed in my PDA either, but in the bestselling book by Sipser they are presented that way. There PDA do not necessarily inspect the topmost stack symbol at every move and can run on empty stack. As a matter of fact their initial configuration has an empty stack. Just like in the picture in the question, that is so typically that style. – Hendrik Jan Jan 11 '16 at 0:08
• I don't think reproducing textbook material is useful, except if we made this a more general reference-question. – Raphael Aug 30 '16 at 9:01

In your example you can easily read from the automaton what its language is.

The standard construction to convert a PDA into a CFG is usually called the triplet construction. In that construction the triplet $[p,A,q]$ represents a computation from state $p$ to state $q$ with symbol $A$ on top of the stack that (eventually) is popped.

But in your first attempt I see you are using a different technique. Presumably you should have a look in the book of Sipser? The variable $A_{ij}$ will generate the strings read on a computation from state $q_i$ to state $q_j$ beginning and ending with the empty stack. (Which is not technically allowed in many other texts.) This construction combines a push of some stack symbol $Y$ with a pop of the same $Y$ elsewehere in the computation. So with the instructions $(q_i,a,q_k,\text{push}Y)$ and $(q_\ell,b,q_j,\text{pop}Y)$ the computation from $q_i$ to $q_j$ is started by reading $a$ pushing $Y$ and continuing from next state $q_k$ we persue the computation until in state $q_\ell$ we pop that same $Y$ read $b$ and move to state $q_j$. This is summarized by the context-free rule $A_{ij}\to a A_{k\ell} b$.

Try this construction, but pick up a copy of your book or lecture notes on the way.