Chapter 6: Context-Free Languages !;! 199
Corollary 2 If G = (Vv, L:. P. 5) is a context-free grammar we can find an
equivalent context-free grammar G l =(V~v, L:, P, 51) without null productions
except 51 - j A when A is in L(G). If 51 - j A is in Pl' 51 does not appear
on the R.H.S. of any production in Pl'
Proof By Corollary 1, we can decide whether A is in L(G).
Case 1 If A is not in L(G), G[ obtained by using Theorem 6.6 is the required
equivalent grammar.
Case 2 If A is in L(G), construct G' = (VV, L:. r. 5) using Theorem 6.6.
L(G') =L(G) - {A}. Define G l = (V N U {51}, L:, PI' 51), where PI = p' U
{51 - j 5. 5 j - j A}. 51 does not appear on the R.H.S. of any production in
Pl. and so G l is the required grammar with L(G l ) = L(G). I
6.3.3 ELIMINATION OF UNIT PRODUCTIONS
A context-free grammar may have productions of the form A - j B, A, B
E Vy.
Consider. for example, G as the grammar 5 - j A, A - j B, B - j C,
C - j a. It is easy to see that L(G) = {a}. The productions 5 - j A, A - j B,
B - j C are useful just to replace 5 by C. To get a terminal string, we need
C - j a. If G j is 5 - j a, then L(G j ) = L(G).
The next construction eliminates productions of the form A - j B.
Definition 6.10 A unit production (or a chain rule) in a context-free
grammar G is a production of the form A - j B. where A and B are variables
in G.
Theorem 6.7 If G is a context-free grammar,we can find a context-free
grammar Gj which has no null productions or unit productions such that
L(G[) = L(G).
Proof We can apply Corollary 2 of Theorem 6.6 to grammar G to get a
grammar G' = (Vy, L:, P. 5) without null productions such that L(G') = L(G).
Let A be any variable in V".
Step 1 COl1stmction of the set of variables derivable from A:
Define Wr(A) recursively as follows:
Wo(A) = {A}
W r + i (A) = Wr(A) u {B E Vv I C - j B is in P with C E Wr(A)}
By definition of R'r(A), W/A) \:: W r + l (A). As Vv is finite. W k + l (A) = Wk(A)
for some k s: IVvJ. So, Wk+iA) = Wr(A) for all j ;:: O. Let W(A) = Wk(A). Then
W(A is the set of all variables derivable from A
Step 2 Construction of A -productions in G j :
The A-productions in G l are either (i) the nonunit production in G' or
(ii) A - j a whenever B - j a is in G with B E W(A) and a .,; VN-
Corollary 2 If G = (Vv, L:. P. 5) is a context-free grammar we can find an
equivalent context-free grammar G l =(V~v, L:, P, 51) without null productions
except 51 - j A when A is in L(G). If 51 - j A is in Pl' 51 does not appear
on the R.H.S. of any production in Pl'
Proof By Corollary 1, we can decide whether A is in L(G).
Case 1 If A is not in L(G), G[ obtained by using Theorem 6.6 is the required
equivalent grammar.
Case 2 If A is in L(G), construct G' = (VV, L:. r. 5) using Theorem 6.6.
L(G') =L(G) - {A}. Define G l = (V N U {51}, L:, PI' 51), where PI = p' U
{51 - j 5. 5 j - j A}. 51 does not appear on the R.H.S. of any production in
Pl. and so G l is the required grammar with L(G l ) = L(G). I
6.3.3 ELIMINATION OF UNIT PRODUCTIONS
A context-free grammar may have productions of the form A - j B, A, B
E Vy.
Consider. for example, G as the grammar 5 - j A, A - j B, B - j C,
C - j a. It is easy to see that L(G) = {a}. The productions 5 - j A, A - j B,
B - j C are useful just to replace 5 by C. To get a terminal string, we need
C - j a. If G j is 5 - j a, then L(G j ) = L(G).
The next construction eliminates productions of the form A - j B.
Definition 6.10 A unit production (or a chain rule) in a context-free
grammar G is a production of the form A - j B. where A and B are variables
in G.
Theorem 6.7 If G is a context-free grammar,we can find a context-free
grammar Gj which has no null productions or unit productions such that
L(G[) = L(G).
Proof We can apply Corollary 2 of Theorem 6.6 to grammar G to get a
grammar G' = (Vy, L:, P. 5) without null productions such that L(G') = L(G).
Let A be any variable in V".
Step 1 COl1stmction of the set of variables derivable from A:
Define Wr(A) recursively as follows:
Wo(A) = {A}
W r + i (A) = Wr(A) u {B E Vv I C - j B is in P with C E Wr(A)}
By definition of R'r(A), W/A) \:: W r + l (A). As Vv is finite. W k + l (A) = Wk(A)
for some k s: IVvJ. So, Wk+iA) = Wr(A) for all j ;:: O. Let W(A) = Wk(A). Then
W(A is the set of all variables derivable from A
Step 2 Construction of A -productions in G j :
The A-productions in G l are either (i) the nonunit production in G' or
(ii) A - j a whenever B - j a is in G with B E W(A) and a .,; VN-