400 g Solutions (or Hints) to Chapter-end Exercises
(b) Step 1 Replace B ~ aSb by B ~ aSC and C ~ b. Rename S,
A, Band C by Aj, A 2 , A 3 and A.j. The resulting grammar is
G[ = ({A j • A 2 • A 3 , A.j}, {a, b}, P lo Ai)
where Pi consists of A[ ~ A 2 A 3 • A 2 ~ A:03
A 2 ~ A 3 A[A 3 , A 2 ~ b, A 3 ~ aA 2 A 4 • A 3 ~ a and A 4 ~ b.
Steps 2, 3 and 4 Step 2 construction is not necessary for G j •
The only A 4 -production. A 4 ~ b, is in proper form. So we go to step
4. The modified A 2 -productions are:
A 2 ~ aA2A,A3 IaA 3 1aA 2 A 4 A 1 A 3 1aA[A 3 1b.
The modified A [-productions are:
A j ~ aA2A4A~31 aA:03\ aA 2 A.jA j A 3 A3 1 aA[A~31 bA3·
Step 5 is not necessary since there is no new variable in the form in
Zi' So an equivalent grammar in GNP is
G 2 = ({A j , A 2 , A 3 • A.j}, {a, b}, P 2 , A[)
where P 2 consists of
A[ ~ aA2A.jA~3 1aA,A 3 I aA2A4AiA3A3 I aAiA~31 bA3
A 2 ~ aA 2 A 4 A 3 IaA 3 1 aA 2 A.+AIA 3 1 aA[A 3 1 b
A 3 ~ aA 2 A 4 1a, A.j ~ b.
6.15 The grammar given in Exercise 6.7 has the following productions:
S ~ aB. S ~ ab, A ~ aAB. A ~ a. B ~ ABb and B ~ b. Of these,
S ~ aBo A ~ aAB. A ~ a and B ~ b are in the required form. So
we replace the terminals which appear in the second and subsequent
places of the R.H.S. of S ~ ab and B ~ ABb by a new variable C
and add a production C ~ b. Renaming S, B. A and C as Aj, A 2 , A 3
and A 4 , the modified productions tum out to be A j ~ aA 2 • A j ~ aA 4 ,
A 3 ~ aA~2' A 3 ~ a. A 2 ~ A:02A.j, A 2 ~ band A 4 ~ b.
This completes the first three steps:
Step 4 A 2 ~ A~2A4 is replaced by A 2 ~ aA~2A2A41 aA~4' The
other productions are in the proper form. The resulting grammar in
GNP has the productions
A j ~ aA 2 1aA 4 . A 2 ~ aA:02A2A4IaA2A4Ib, A 3 ~ aA~2Ia, A 4 ~ b.
The grammar in Exercise 6.10 has unit productions. Eliminating unit
productions, we get an equivalent grammar G, where
G = ({S, A. B. C, D. E}, {a. b}, P. S)
where P consists of 5 ~ AB. A ~ a, B ~ a I b, C ~ a, D ~ a
and E ~ a. Rename S. A, B. C, D and E as A j , A 2 , A 3 , A 4 , As and
A 6•
(b) Step 1 Replace B ~ aSb by B ~ aSC and C ~ b. Rename S,
A, Band C by Aj, A 2 , A 3 and A.j. The resulting grammar is
G[ = ({A j • A 2 • A 3 , A.j}, {a, b}, P lo Ai)
where Pi consists of A[ ~ A 2 A 3 • A 2 ~ A:03
A 2 ~ A 3 A[A 3 , A 2 ~ b, A 3 ~ aA 2 A 4 • A 3 ~ a and A 4 ~ b.
Steps 2, 3 and 4 Step 2 construction is not necessary for G j •
The only A 4 -production. A 4 ~ b, is in proper form. So we go to step
4. The modified A 2 -productions are:
A 2 ~ aA2A,A3 IaA 3 1aA 2 A 4 A 1 A 3 1aA[A 3 1b.
The modified A [-productions are:
A j ~ aA2A4A~31 aA:03\ aA 2 A.jA j A 3 A3 1 aA[A~31 bA3·
Step 5 is not necessary since there is no new variable in the form in
Zi' So an equivalent grammar in GNP is
G 2 = ({A j , A 2 , A 3 • A.j}, {a, b}, P 2 , A[)
where P 2 consists of
A[ ~ aA2A.jA~3 1aA,A 3 I aA2A4AiA3A3 I aAiA~31 bA3
A 2 ~ aA 2 A 4 A 3 IaA 3 1 aA 2 A.+AIA 3 1 aA[A 3 1 b
A 3 ~ aA 2 A 4 1a, A.j ~ b.
6.15 The grammar given in Exercise 6.7 has the following productions:
S ~ aB. S ~ ab, A ~ aAB. A ~ a. B ~ ABb and B ~ b. Of these,
S ~ aBo A ~ aAB. A ~ a and B ~ b are in the required form. So
we replace the terminals which appear in the second and subsequent
places of the R.H.S. of S ~ ab and B ~ ABb by a new variable C
and add a production C ~ b. Renaming S, B. A and C as Aj, A 2 , A 3
and A 4 , the modified productions tum out to be A j ~ aA 2 • A j ~ aA 4 ,
A 3 ~ aA~2' A 3 ~ a. A 2 ~ A:02A.j, A 2 ~ band A 4 ~ b.
This completes the first three steps:
Step 4 A 2 ~ A~2A4 is replaced by A 2 ~ aA~2A2A41 aA~4' The
other productions are in the proper form. The resulting grammar in
GNP has the productions
A j ~ aA 2 1aA 4 . A 2 ~ aA:02A2A4IaA2A4Ib, A 3 ~ aA~2Ia, A 4 ~ b.
The grammar in Exercise 6.10 has unit productions. Eliminating unit
productions, we get an equivalent grammar G, where
G = ({S, A. B. C, D. E}, {a. b}, P. S)
where P consists of 5 ~ AB. A ~ a, B ~ a I b, C ~ a, D ~ a
and E ~ a. Rename S. A, B. C, D and E as A j , A 2 , A 3 , A 4 , As and
A 6•