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$
7	$bbbaa$	$X_1$
8	$bbaa$	$\lambda_2$
9	$baa$	$Y_1$
10	$aa$	$Y_2Y_1$
11	$a$	$Y_1$
12	$\lambda$	$\lambda$

We have numbered the stack variables (and the lambdas) with subscripts according to the order in which they appear on the stack so we can inspect their stack lifetimes. As always, the stack begins and ends empty, and in between, it grows and shrinks in size repeatedly. A stack variable’s lifetime is the number of steps from when it is first pushed until it is removed from the stack. The lifetimes of the stack variables in the above table appear in the following table.

Stack Variable	Lifetime (In Steps)	Step Range
$X_1$	7	1–7
$X_2$	5	2–6
$X_3$	1	3–3
$X_4$	1	5–5
$Y_1$	3	9–11
$Y_2$	1	10–10

From the time the first variable, $X_1$, appears on the stack until it is removed, three other $X$’s ($X_2$ ...