Chapter 6: Context-Free Languages ,!;l, 201
,i;
Let i be the smallest index such that Ct i ~ Ct i + 1 is obtained by a unit
production and j be the smallest index greater than i such that Ctj ~ Cti+J is
x
G
obtained by a nonunit production. So, S ~ ai, and aj ~ aJ'+1 can be
G,
' G' .
written as
ai = H'iA;{3 i =} wi Ai+!f3i =} .. , =} Wi A jf3i =} wir f3i = CXj+!
A j E W(A i ) and A j ~ r is a nonunit production. Therefore, A j ~ r is a
production in PI' Hence, Ctj ~ aj+I' Thus, we have S ~ aj+I'
. G,
'
G,
Repeating the argument whenever some unit production occurs in the
remaining part of the derivation, we can prove that S ~ a" = w, This proves
G,
L(G') s;;;; L(G). I
Corollary If G is a context-free grammar, we can construct an equivalent
grammar G' which is reduced and has no null productions or unit productions.
Proof We construct G] in the following way:
Step 1 Eliminate null productions to get G] (Theorem 6.6 or Corollary 2 of
this theorem).
Step 2 Eliminate unit productions in G] to get G 2 (Theorem 6.7).
Step 3 Construct a reduced grammar G' equivalent to G] (Theorem 6.5). G'
is the required grammar equivalent to G.
Note: We have to apply the constructions only in the order given in the
corollary of Theorem 6.7 to simplify grammars. If we change the order we
may not get the grammar in the most simplified form (refer to Exercise 6.11).
6.4 NORMAL FORMS FOR CONTEXT-FREE GRAMMARS
In a context-free grammar. the R.H.S. of a production can be any string of
variables and terminals. When the productions in G satisfy certain restrictions,
then G is said to be in a 'normal form'. Among several 'normal forms' we study
two of them in this section-the Chomsky normal form (CNF) and the
Greibach nOlmal form.
6.4.1 CHOMSKY NORMAL FORM
In the Chomsky normal form (CNF). we have restrictions on the length of
R.H.S. and the nature of symbols in the R.H.S. of productions.
DefInition 6.11 A context-free grammar G is in Chomsky normal form if
every production is of the form A ~ G, or A ~ Be, and S ~ A is in G if
,i;
Let i be the smallest index such that Ct i ~ Ct i + 1 is obtained by a unit
production and j be the smallest index greater than i such that Ctj ~ Cti+J is
x
G
obtained by a nonunit production. So, S ~ ai, and aj ~ aJ'+1 can be
G,
' G' .
written as
ai = H'iA;{3 i =} wi Ai+!f3i =} .. , =} Wi A jf3i =} wir f3i = CXj+!
A j E W(A i ) and A j ~ r is a nonunit production. Therefore, A j ~ r is a
production in PI' Hence, Ctj ~ aj+I' Thus, we have S ~ aj+I'
. G,
'
G,
Repeating the argument whenever some unit production occurs in the
remaining part of the derivation, we can prove that S ~ a" = w, This proves
G,
L(G') s;;;; L(G). I
Corollary If G is a context-free grammar, we can construct an equivalent
grammar G' which is reduced and has no null productions or unit productions.
Proof We construct G] in the following way:
Step 1 Eliminate null productions to get G] (Theorem 6.6 or Corollary 2 of
this theorem).
Step 2 Eliminate unit productions in G] to get G 2 (Theorem 6.7).
Step 3 Construct a reduced grammar G' equivalent to G] (Theorem 6.5). G'
is the required grammar equivalent to G.
Note: We have to apply the constructions only in the order given in the
corollary of Theorem 6.7 to simplify grammars. If we change the order we
may not get the grammar in the most simplified form (refer to Exercise 6.11).
6.4 NORMAL FORMS FOR CONTEXT-FREE GRAMMARS
In a context-free grammar. the R.H.S. of a production can be any string of
variables and terminals. When the productions in G satisfy certain restrictions,
then G is said to be in a 'normal form'. Among several 'normal forms' we study
two of them in this section-the Chomsky normal form (CNF) and the
Greibach nOlmal form.
6.4.1 CHOMSKY NORMAL FORM
In the Chomsky normal form (CNF). we have restrictions on the length of
R.H.S. and the nature of symbols in the R.H.S. of productions.
DefInition 6.11 A context-free grammar G is in Chomsky normal form if
every production is of the form A ~ G, or A ~ Be, and S ~ A is in G if