Theory of Computation

4.3  THE PDA-ACCEPTABLE LANGUAGES ARE THE CONTEXT FREE LANGUAGES

We have defined grammars, in particular, CFG in 3.4.0.7. We will see in this section that CFG are an alternative formalism to that of PDA. They define exactly the same languages. First off we note that for any CFG, G = , Σ, S, , we can assume without loss of generality that its instructions have two possible forms: A → a, where a Σ ∪ {}, and A → X₁ X₂ · · · X_n—the right hand side being a string of X_i, each of which is a nonterminal.

Indeed, if G does not already have the desired rule structure, we add new nonterminals, Y^(a), one for each a Σ. We then replace each rule A → α—where α contains at least one nonterminal—with A → α′, where α′ is the result of replacing each a occurring in α (a Σ) by Y^(a). Finally, we add the rules ...