202 Q Theory of Computer Science
A E L(G). When A is in L(G), we assume that S does not appear on the
RH.S. of any production.
For example, consider G whose productions are S ~ AB IA, A ~ a,
B ~ b. Then G is in Chomsky normal form.
Remark For a grammar in CNF, the derivation tree has the following
property: Every node has atmost two descendants-either two internal vertices
or a single leaf.
When a grammar is in CNF, some of the proofs and constructions are
simpler.
Reduction to Chomsky Normal Form
Now we develop a method of constructing a grammar in CNF equivalent to a
given context-free grammar. Let us first consider an example. Let G be S ~
ABC IaC, A ~ a. B ~ b, C ~ c. Except S ~ aC IABC, all the other
productions are in the form required for CNF. The terminal a in S ~ aC can
be replaced by a new variable D. By adding a new production D ~ a, the effect
of applying S ~ aC can be achieved by S ~ DC and D ~ a. S ~ ABC is not
in the required form. and hence this production can be replaced by S ~ AE and
E ~ Be. Thus, an equivalent grammar is S ~ AE IDC, E ~ BC, A ~ a,
B ~ b. C ~ c, D ~ a.
The techniques applied in this example are used in the following theorem.
Theorem 6.8 (Reduction to Chomsky normal form). For every context-free
grammar, there is an equivalent grammar G 2 in Chomsky normal form.
Proof (Construction of a grammar in CNF)
Step 1 Elimination of null productions and unit productions:
We apply Theorem 6.6 to eliminate null productions. We then apply
Theorem 6.7 to the resulting grammar to eliminate chain productions. Let the
grammar thus obtained be G = (V"" L, P, S).
Step 2 Elimination of terminals on R.H.S.:
We define G 1 =(V"" L, PI, S'), where p] and V;,vare constructed as follows:
(i) All the productions in P of the form A ~ a or A ~ BC are included
in P lo All the variables in Vv are included in V;",.
(ii) Consider A ~ X j X 2 ..• X n with some terminal on RH.S. If Xi isa
terminaL say ai, add a new variable C a to V;", and C a ~ ai to Pl'
I
I
In production A ~ X j X 2 ... Xii' every terminal on R.H.S. is replaced
by the corresponding new variable and the variables on the RH.S. are
retained. The resulting production is added to p]. Thus, we get
G 1 = (V:"', L, Ph S).
Step 3 Restricting the number of variables on R.H.S.:
For any production in Plo the R.H.S. consists of either a single terminal (or
A E L(G). When A is in L(G), we assume that S does not appear on the
RH.S. of any production.
For example, consider G whose productions are S ~ AB IA, A ~ a,
B ~ b. Then G is in Chomsky normal form.
Remark For a grammar in CNF, the derivation tree has the following
property: Every node has atmost two descendants-either two internal vertices
or a single leaf.
When a grammar is in CNF, some of the proofs and constructions are
simpler.
Reduction to Chomsky Normal Form
Now we develop a method of constructing a grammar in CNF equivalent to a
given context-free grammar. Let us first consider an example. Let G be S ~
ABC IaC, A ~ a. B ~ b, C ~ c. Except S ~ aC IABC, all the other
productions are in the form required for CNF. The terminal a in S ~ aC can
be replaced by a new variable D. By adding a new production D ~ a, the effect
of applying S ~ aC can be achieved by S ~ DC and D ~ a. S ~ ABC is not
in the required form. and hence this production can be replaced by S ~ AE and
E ~ Be. Thus, an equivalent grammar is S ~ AE IDC, E ~ BC, A ~ a,
B ~ b. C ~ c, D ~ a.
The techniques applied in this example are used in the following theorem.
Theorem 6.8 (Reduction to Chomsky normal form). For every context-free
grammar, there is an equivalent grammar G 2 in Chomsky normal form.
Proof (Construction of a grammar in CNF)
Step 1 Elimination of null productions and unit productions:
We apply Theorem 6.6 to eliminate null productions. We then apply
Theorem 6.7 to the resulting grammar to eliminate chain productions. Let the
grammar thus obtained be G = (V"" L, P, S).
Step 2 Elimination of terminals on R.H.S.:
We define G 1 =(V"" L, PI, S'), where p] and V;,vare constructed as follows:
(i) All the productions in P of the form A ~ a or A ~ BC are included
in P lo All the variables in Vv are included in V;",.
(ii) Consider A ~ X j X 2 ..• X n with some terminal on RH.S. If Xi isa
terminaL say ai, add a new variable C a to V;", and C a ~ ai to Pl'
I
I
In production A ~ X j X 2 ... Xii' every terminal on R.H.S. is replaced
by the corresponding new variable and the variables on the RH.S. are
retained. The resulting production is added to p]. Thus, we get
G 1 = (V:"', L, Ph S).
Step 3 Restricting the number of variables on R.H.S.:
For any production in Plo the R.H.S. consists of either a single terminal (or