From PDA to CFG (General Case)

Learn about the general case of conversion of a PDA to a CFG.

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 Leq={na(w)=nb(w)w(a+b)}L_{eq} = \{n_a(w)\:=\:n_{b}(w)\:|\:w \in (a+b)^* \} found in the figure below.

Get hands-on with 1200+ tech skills courses.