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*_{1} *X*_{2} · · · *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 ...

Start Free Trial

No credit card required