Chapter 6: Context-Free Languages ~ 203
A in S ~ A) or two or more variables. We define G 2 = (V~~, L, P2. S) as
follows:
(i) All productions in p[ are added to P 2 if they are in the required form.
All the variables in V: v are added to ~~(:.
(ii) Consider A ~ A j A 2 .•• Am. where m ~ 3. We introduce new
productions A ~ A[C[. C j ~ A 2 C 2 • ... , C m - 2 ~ Am-lAm and
new variables C j , C 2 • . . . , C m - 2 . These are added to P" and VIVo
respectively.
Thus. we get G 2 in Chomsky normal form.
Before proving that G 2 is the required equivalent grammar. we apply the
construction to the context-free grammar given m Example 6.11.
EXAMPLE 6.11
Reduce the following grammar G to CNF. G is 5 ~ aAD, A ~ aB I bAB,
B ~ b. D ~ d.
Solution
As there are no null productions or unit productions, we can proceed to step 2.
Step 2 Let G[ = (V\. {a. b. el}, Pj. 5). where P l and V N are constructed
as follows:
(i) B ~ b, D ~ d are included in Pl'
(ii) 5 ~ aAD gives rise to 5 ~ CuAD and C u ~ a.
A ~ aB gives rise to A ~ CuB.
A ~ bAB gives rise to A ~ ChAB and C h ~ b.
V: v = {5. A. B. D. Cu' C h }.
Step 3 P l consists of 5 ~ CuAD, A ~ C"B IChAB, B ~ b. D ~ d, C u ~ a.
C/J ~ b.
A ~ CuB. B ~ b, D ~ d, C u ~ a, C h ~ b are added to P 2
5 ~ CuAD is replaced by 5 ~ CuC j and C l ~ AD.
A. ~ C/JAB is replaced by A ~ C/JC 2 and C 2 ~ AB.
Let
G 2 = ({5. A. B, D. C u ' C h • C l • CJ. {a. b, d}, P 2 • 5)
where P 2 consists of 5 ~ C"C lo A ~ CuB I C/JC 2 • Cj ~ AD. C 2 ~ AB,
B ~ b, D ~ el. C u ~ a. C h ~ b. G 2 is in CNF and equivalent to G.
Step 4 L(G) = L(G 2 ). To complete the proof we have to show that L(G) =
L(G j ) = L(G 2 )·
fo show that L(G) ~ L(G[). we start with H E L(G). If A ~ X j X 2 ... XII
is used in the derivation of 1\'. the same effect can be achieved by using the
corresponding production in P j and the productions involving the new
variables. Hence, A ~ X j X 2 ... XII' Thus. L(G) ~ L(G l )·
G
A in S ~ A) or two or more variables. We define G 2 = (V~~, L, P2. S) as
follows:
(i) All productions in p[ are added to P 2 if they are in the required form.
All the variables in V: v are added to ~~(:.
(ii) Consider A ~ A j A 2 .•• Am. where m ~ 3. We introduce new
productions A ~ A[C[. C j ~ A 2 C 2 • ... , C m - 2 ~ Am-lAm and
new variables C j , C 2 • . . . , C m - 2 . These are added to P" and VIVo
respectively.
Thus. we get G 2 in Chomsky normal form.
Before proving that G 2 is the required equivalent grammar. we apply the
construction to the context-free grammar given m Example 6.11.
EXAMPLE 6.11
Reduce the following grammar G to CNF. G is 5 ~ aAD, A ~ aB I bAB,
B ~ b. D ~ d.
Solution
As there are no null productions or unit productions, we can proceed to step 2.
Step 2 Let G[ = (V\. {a. b. el}, Pj. 5). where P l and V N are constructed
as follows:
(i) B ~ b, D ~ d are included in Pl'
(ii) 5 ~ aAD gives rise to 5 ~ CuAD and C u ~ a.
A ~ aB gives rise to A ~ CuB.
A ~ bAB gives rise to A ~ ChAB and C h ~ b.
V: v = {5. A. B. D. Cu' C h }.
Step 3 P l consists of 5 ~ CuAD, A ~ C"B IChAB, B ~ b. D ~ d, C u ~ a.
C/J ~ b.
A ~ CuB. B ~ b, D ~ d, C u ~ a, C h ~ b are added to P 2
5 ~ CuAD is replaced by 5 ~ CuC j and C l ~ AD.
A. ~ C/JAB is replaced by A ~ C/JC 2 and C 2 ~ AB.
Let
G 2 = ({5. A. B, D. C u ' C h • C l • CJ. {a. b, d}, P 2 • 5)
where P 2 consists of 5 ~ C"C lo A ~ CuB I C/JC 2 • Cj ~ AD. C 2 ~ AB,
B ~ b, D ~ el. C u ~ a. C h ~ b. G 2 is in CNF and equivalent to G.
Step 4 L(G) = L(G 2 ). To complete the proof we have to show that L(G) =
L(G j ) = L(G 2 )·
fo show that L(G) ~ L(G[). we start with H E L(G). If A ~ X j X 2 ... XII
is used in the derivation of 1\'. the same effect can be achieved by using the
corresponding production in P j and the productions involving the new
variables. Hence, A ~ X j X 2 ... XII' Thus. L(G) ~ L(G l )·
G