Therefore, the new set of productions $
P for the grammar equivalent to the
given CFG is
S
AB A B
S
aAA aA a
B
bBB bB b
→
→
→
| |
| |
| | .
2.5 NORMAL FORMS
Two kinds of normal forms viz., Chomsky Normal Form and Greibach
Normal Form (GNF) are considered here.
2.5.1 Chomsky Nor mal Form (CNF)
Any context-free language L without any λ-production is generated by a
grammar is which productions are of the form A BC
→
or A a
→ , where
A B V N
,
,
∈
and a V T
∈ .
Pro ce dure to find Equiv a lent Gram mar in CNF
(i) Eliminate the unit productions, and λ-productions if any,
(ii) Eliminate the terminals on the right hand side of length two or
more.
(iii) Restrict the number of variables on the right hand side of
productions to two.
Proof:
For Step (i): Apply the following theorem:
“Every context free language can be generated by a grammar with no
useless symbols and no unit productions”.
At the end of this step the RHS of any production has a single terminal or
two or more symbols. Let us assume the equivalent resulting grammar as
G V V P S
N
T
= ( , , , ).
For Step (ii): Consider any production of the form
A
y y
y
m
m
→
≥
1 2
2
KK ,
.
If y 1 is a terminal, say ‘a’, then introduce a new variable B a and a
production
B
a
a →
Repeat this for every terminal on RHS.
Let P′ be the set of productions in P together with the new productions
142
Theory of Automata, Formal Languages and Computation