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.