From PDA to CFG (General Case)

Converting an arbitrary PDA to CFG

To convert an arbitrary PDA to a CFG, we somehow need to relate the states and transitions of the PDA, including stack operations, to variables and rules in a CFG. This is a tall order but a doable one. To understand the algorithm, we need to take a deeper look at stack behavior in PDAs. We start with the simple, one-state PDA for $L_{eq} = \{n_a(w)\:=\:n_{b}(w)\:|\:w \in (a+b)^* \}$ found in the figure below.

While referring to this figure, let’s study the following trace of $aaababbbbbaa$.

Step	Input	Stack
0	$aaababbbbbaa$	$\lambda_1$
1	$aababbbbbaa$	$X_1$
2	$ababbbbbaa$	$X_2X_1$
3	$babbbbbaa$	$X_3X_2X_1$
4	$abbbbbaa$	$X_2X_1$
5	$bbbbbaa$	$X_4X_2X_1$
6	$bbbbaa$	$X_2X_1$

...