212 ~ Theory of Computer Science
EXAMPLE 6.1 7
Find a grammar in G:t\TF equivalent to the grammar
E ---+ E + TIT, T ---+ T*FIF. F ---+ (E)la
Solution
Step 1 We first eliminate unit productions. Hence
So.
So.
Wo(E) = {EL
WI(E) = {E} u {T} = {E, T}
W:(E) = {E, T} u {F} = {E, T, F}
WeE) = {E, T, F}
Thus.
WoCT) = {T},
WI(T) = {T} u {F} = {T. F}
(6.14)
WCT) = {T. F}
Wo(F) = {F},
WI(F) = {F} = W(F)
The equivalent grammar without unit productions is, therefore, G] =(V N ,
L, Pl' S), where PI consists of
(i) E ---+ E + TIT"FI(E)la
(ii) T ---+ T * FI (E) I a. and
(iii) F ---+ (E)! a.
We apply step 2 of reduction to CNF. We introduce new variables A, B,
C con'esponding to +. '.). The modified productions are
(i) E ---+ EATI TBFI (Eq a
(ii) T ---+ TBF 1 (EC 1 a
(iii) F ---+ (EC Ia
(iv) A ---+ +. B ---+ ", C ---+ )
The variables A. B. C F. T and E are renamed as AI' A:, A 3 , A 4 . As, A 6 .
Then the productions become
A 1 ---+ +,
Ao ---+ *.
A 3 ---+).
A 4 ---+ (A03 1 a
(6.13)
As ---+ AsA:A+ I(A~31 a
A 6 ---+ AeA lAs IA s A:A4 ! (A~31 a
Step 2 We have to modify only the A s - and A 6 -productions. As ---+ AsA:Aj
can be modified by using Lemma 6.2. The resulting productions are
A s ---+ (A 6 A 3 Ia.
As ---+ (A~3ZslaZs
Zs ---+ A :A 4 1 A :A 4 Z S
A 6 ---+ A s A:A 4 can be modified by using Lemma 6.1. The resulting
productions are
A 6 ---+ (A~:A:A41 aA:A4 1 (A e ;1.3 Z s A : A 41 aZsA:A4
A 6 ---+ (A 6"4.3 1 a are in the proper fonn.