Solutions (or Hints) to Chapter-end Exercises g 399
Step 3 G: = (~<:, {a, b, +, *}. P:, S), where P 2 is constructed as
follows:
(i) S ~ a, S ~ b, A ~ + and B ~ * are included in P 2 •
(ii) S ~ SAS and S ~ SBS give rise to S ~ SA b A j ~ AS,
S ~ SBj. B j ~ BS.
The required grammar in CNF is
G 2 = ({S, A, B, Aj, Bd, {a, b, +, *}. P b S)
where P 2 consists of
S ~ alblSAdSBj, A ~ +, B ~ *, A j ~ AS and B j ~ BS
6.14 (a) Rename S as Aj, By Remark following Theorem 6.9, it is enough
to replace terminals by new variables to get an equivalent grammar
G j. Now, G j is defined as
G j = ({A j, A 2 , A 3 }, {O, I}, P b A j)
where Pj consists of
A j ~ AjAIiA2AjA3IA2A3' A 2 ~ 0 and A 3 ~ 1
This completes step 1.
Step 2 All productions of G j except A j ~ A jA j are in proper form.
Applying Lemma 6.2 to A j ~ AjA]> we get a new variable Zj and
new productions A j ~ A 2 A jA 3 Z j l A 2 A 3 Zj, Zj ~ Aj, Zj ~ AjZj • The
new grammar IS
G 2 = ({A b A 2 , A 3 , Zd, {a, b}, P 2 , A j)
where P: consists of
A j ~ A2AjA31A2A31A2AtA3ZjlA2A3Zj
Zj ~ AjZj, Zj ~ A j, A 2 ~ 0 and A j ~ 1
Step 3 As A 3 -productions and Arproductions are in proper form we
have to modify only the A j-productions using Lemma 6.1. So the
modified A j-productions are
A j ~ OA jA 3 1 OA310AjA3ZjlOA3Zj
Step 4 The productions Zj ~ A j and Zj ~ A jZj are modified using
Lemma 6.1. They are:
Zj ~ OA jA 3 1 OA 3 1 OA jA 3 Z j l OA 3 Z j
Zj ~ OA jA 3 Z j I OA 3 Z j I OA jA 3 Z jZ j IOA 3 Z jZ j
Thus the required equivalent grammar in GNF is
G 3 = ({A j• A:> A 3 • Zd. {O, I}. P 3 , A j). where P j consists of
A j ~ OA j A 3 1 OA 3 1 OA j A 3 Zj l OA 3 Z j
A, ~ 0, A 3 ~ 1
Zj ~ OA j A 3 1 OA 3 1OA jA 3 Z j I OA 3 Z j
Zj ~ OA jA 3 Z j IOA 3 Z j I OA j A 3 Z jZ j IOA 3 Z jZ j