(a) Empty Pro duc tion Removal
If the empty string does not belong to a language, then there is no way to
eliminate production of the form A → λ from the grammar.
If the empty string belongs to a language, then we can eliminate λ from all
productions same for the single productions S → λ. In this case we can
eliminate any occurrences of S from the right-hand-side of productions.
(b) Unit Pro duc tion 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.
3.2.2 Nor mal Forms of Con text-Free Gram mars
(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 λ can be put into Chomsky Normal Form.
(b) Greibach Nor mal 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.
3.2.3 CFG to NPDA
For any context-free grammar in GNF, it is easy to build an equivalent
nondeterministic pushdown automaton (NPDA).
Pushdown Automata
167