Converting a PDA to a CFG

We will proceed in a manner analogous to Kleene's theorem for regular languages: that is, we will try to slice up the machine into various components (each of which has a corresponding language), and then put them back together again using a CFG.

For any PDA, let us define the language

$$\langle P,Q,t\rangle = \left\{ \begin{array}{c} x \in \Sigma... ...n from the top of the stack in the process}\end{array}\right\}$$

Now, given any PDA, we construct a context-free grammar which accepts the same language as follows:

• The terminal symbols are just the input symbols of the PDA
• The non-terminal symbols are all triples of the form $\langle P,Q,t\rangle$, for each state $P$ and $Q$, and each stack symbol $t$
• If $S$ and $F$ are the start and finish states respectively of the PDA, then the start symbol of the CFG is $\langle S,F,\varepsilon\rangle$.
• The production rules are as follows:
  • For each transition of the form $(P,a,t) \mapsto (R,\beta_1\cdots\beta_j)$, add all rules of the form
    
    $$\langle P,Q_j,t\rangle \rightarrow a.\langle R,Q_1,\beta_1\ra... ...Q_1,Q_2,\beta_2\rangle\ldots \langle Q_{j-1},Q_j,\beta_j\rangle$$
    
    
    where the $Q_i$ can be any state in the machine
  • For each transition of the form $(P,a,t) \mapsto (R,\varepsilon)$, add all rules of the form
    
    $$\langle P,R,t\rangle \rightarrow a$$