Relation Between Pda And Context Free Language

Simplifying CFGs: The productions of context-free grammars can be coerced into a variety of forms without affecting the expressive power of the grammar.

(a) Empty Production Removal

If the empty string does not belong to a language, then there is no way to eliminate production of the form A-> l from the grammar.

If the empty string belongs to a language, then we can eliminate l from all productions same for the single productions S -> l. In this case we can eliminate any occurrences of S from the right-hand-side of productions.

(b) Unit Production Removal

We can eliminate productions of the form A-> B from a CFG.

(c) Left Recursion Removal

A variable A is left-recursive if it occurs in a production of the form

A-> Ax

for any x Î(V ÈT )* . A grammar is left-recursive if it contains at least one left-recursive variable. Every CFL can be represented by a grammar that is not left-recursive.

Normal Forms of Context-Free Grammars

(a) Chomsky Nor mal Form

A grammar is in Chomsky Normal form if all productions are of the form

A-> BC

or A-> a

where A, B and C are variables and ‘a’ is a terminal. Any context-free grammar that does not contain l can be put into Chomsky Normal Form.

(b) Greibach Normal Form (GNF)

A grammar is in Greibach Normal Form if all productions are of the form

A-> ax

where ‘a’ is a terminal and x ÎV * .

Grammars in Greibach Normal Form are much longer than the CFG from which they were derived. GNF is useful for proving the equivalence of NPDA and CFG.

Thus GNF is useful in converting a CFG to NPDA.