O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 = ImagesImages, Σ, S, ImagesImages, we can assume without loss of generality that its instructions have two possible forms: Aa, where a Images Σ ∪ {images}, and AX1 X2 · · · Xn—the right hand side being a string of Xi, 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 Images Σ. 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required