Chapter 6: Context-Free Languages J;! 205
Solution
As there are no unit productions or null productions, we need not carry out
step 1. We proceed to step 2.
Step 2 Let G j = (V ' y {a, b}, PI' S), where Pj and V: v are constructed as
follows:
(i) A ~ a, B ~ b are added to Pl'
(ii) S ~ aAbB, A ~ aA, B ~ bB yield S ~ CaACbB. A ~ CaA.
B ~ C;,B. C{/ ~ a. C b ~ b.
V'v = {S, A, B, C", C b }·
Step 3 PI consists of S ~ CaACbB, A ~ CaA, B ~ C;,B, C a ~ a.
C b ~ b, A ~ a, B ~ b.
S ~ C{/AC/JB is replaced by S ~ CaC] , C 1 ~ AC~. C e ~ CbB
The remaining productions in P j are added to Pc. Let
G: = ({S. A. B. CO' C/J' CI' C e }, {a, b}, Pc. S),
where Pc consists of S ~ CaCjo C i ~ ACe, C e ~ C/JB, A ~ CaA. B ~ C/JB.
C a ~ a, C b ~ b. A ~ a. and B ~ b.
G: is in C:I'<'F and equivalent to the given grammar.
,
EXAMPLE 6.13
Find a grammar in C:I'<'F equivalent to the grammar
Solution
S ~ -S I[s :::J) S] Ipi q
(S being the only variable)
As the given grammar has no unit or null productions, we omit step 1 and
proceed to step 2.
Step 2 Let G j = (V\, L. PI' S). where Pj and V~\ are constructed as fonows:
(i) S ~ pi q are added to Pj.
(ii) S ~ - S induces S ~ AS and A ~ -.
(iii) S ~ [S :::J S] induces S ~ BSCSD, B ~ [,C ~ :::J. D ~]
\1'\ = {So A. B. C. D}
Step 3 Pj consists of S ~ plq. S ~ AS. A ~ -, B ~ LC ~:::J, D ~].
S ~ BSCSD.
S ~ BSCSD is replaced by S ~ BC I , Cj ~ SCe' C e ~ CC 3 , C 3 ~ SD.
Let
G e = ({S, A. B. C. D, C I , C:, C 3 }. L, Pc, S)
where P: consists of S ~ plq[AS[BC j , A ~ -, B ~ [. C ~ :::J, D ~],
C I ~ SCe' C: ~ CC 3 , C 3 ~ SD. G: is in CNF and equivalent to the given
grammar.