Solutions (or Hints) to Chapter-end Exercises ~ 401
Thus P consists of A j ~ A 2 A 3 , A 2 ~ a, A 3 ~ a Ib, A 4 ~ a, As ~ a
and A 6 ~ a.
We have to modify only A j ~ A 2 A 3 using Lemma 6.1.
Thus an equivalent grammar in GNP has the following productions:
A j ~ aA 3 , A 2 ~ a. A 3 ~ a Ib, A 4 ~ a, As ~ a and A 6 ~ a.
6.16. (a) The given language is generated by a grammar whose productions
are S ~ aSalbSblc.
Step 2 (i) S ~ c is in Pj
(ii) S ~ aSa and S ~ bSb give rise to
S ~ ASA, S ~ BSB, A ~ a. B ~ b in P j
Thus G j = ({S, A, B}, {a, b, c}, Pj, S), where P j consists of
S ~ ASA IBSB Ic, A ~ a and B ~ b.
Step 3 The equivalent grammar G 2 in CNP is defined by
G 2 = ({S, A, B. A j , Bd, {a, b, c}, P 2 , S), where P 2 consists of
S ~ AA j, A j ~ SA, S ~ BB b B j ~ SB. A ~ a, B ~ b, S ~ c.
(b) The grammar generating the given set is having the productions
S ~ bAlaB. A ~ bAAlaSla, B ~ aBBlbSlb.
Step 2 The productions obtained in this step are:
S ~ BlA, B j ~ b, S ~ AjB, A j ~ a, A ~ BjAA, A ~ AjS,
A ~ a, B ~ AjBB, B ~ BjS, B ~ b.
Step 3 The equivalent grammar in CNP is given by
G 2 = (V~0, (a, b}. P 2 , S), where P 2 consists of
(i) S ~ BjA, B j ~ b, S ~ AlB, A j ~ a, A ~ AjS, A ~ a,
B ~ BjS, B ~ b
(ii) A ~ BjCj, C j ~ AA, B ~ A j C 2 , C 2 ~ BB (corresponding to
A ~ BjAA and B ~ AjBB).
6.17 (a) The grammar generating the given language has the productions
S ~ aSa, S ~ bSb, S ~ c. The first two productions will be in GNP
if the last symbols on R.H.S. are variables. Hence S ~ aSa, S ~ bSb
can be replaced by S ~ aSA, A ~ a, S ~ bSB, B ~ b. Hence
G' = ({S, A, B}, {a, b}, r, S), where P' consists of S ~ aSA I bSB,
S ~ c, A ~ a, B ~ b is in GNP and is generating the given
language.
(b) The given language is generated by
G = ({S, A. B}, {a, b}, P, S), where P consists of
S ~ bA IaB, A ~ bAA Ias Ia. B ~ aBB IbS Ib. This itself is in GNP.
(c) The given language is generated by a grammar whose productions
are S ~ aAb. S ~ aA, A ~ aA, A ~ a, S ~ a, S ~ bB, B ~ b
and S ~ b. Of these productions we have to modify only one
production namely, S ~ aSb. This is done by replacing this
Thus P consists of A j ~ A 2 A 3 , A 2 ~ a, A 3 ~ a Ib, A 4 ~ a, As ~ a
and A 6 ~ a.
We have to modify only A j ~ A 2 A 3 using Lemma 6.1.
Thus an equivalent grammar in GNP has the following productions:
A j ~ aA 3 , A 2 ~ a. A 3 ~ a Ib, A 4 ~ a, As ~ a and A 6 ~ a.
6.16. (a) The given language is generated by a grammar whose productions
are S ~ aSalbSblc.
Step 2 (i) S ~ c is in Pj
(ii) S ~ aSa and S ~ bSb give rise to
S ~ ASA, S ~ BSB, A ~ a. B ~ b in P j
Thus G j = ({S, A, B}, {a, b, c}, Pj, S), where P j consists of
S ~ ASA IBSB Ic, A ~ a and B ~ b.
Step 3 The equivalent grammar G 2 in CNP is defined by
G 2 = ({S, A, B. A j , Bd, {a, b, c}, P 2 , S), where P 2 consists of
S ~ AA j, A j ~ SA, S ~ BB b B j ~ SB. A ~ a, B ~ b, S ~ c.
(b) The grammar generating the given set is having the productions
S ~ bAlaB. A ~ bAAlaSla, B ~ aBBlbSlb.
Step 2 The productions obtained in this step are:
S ~ BlA, B j ~ b, S ~ AjB, A j ~ a, A ~ BjAA, A ~ AjS,
A ~ a, B ~ AjBB, B ~ BjS, B ~ b.
Step 3 The equivalent grammar in CNP is given by
G 2 = (V~0, (a, b}. P 2 , S), where P 2 consists of
(i) S ~ BjA, B j ~ b, S ~ AlB, A j ~ a, A ~ AjS, A ~ a,
B ~ BjS, B ~ b
(ii) A ~ BjCj, C j ~ AA, B ~ A j C 2 , C 2 ~ BB (corresponding to
A ~ BjAA and B ~ AjBB).
6.17 (a) The grammar generating the given language has the productions
S ~ aSa, S ~ bSb, S ~ c. The first two productions will be in GNP
if the last symbols on R.H.S. are variables. Hence S ~ aSa, S ~ bSb
can be replaced by S ~ aSA, A ~ a, S ~ bSB, B ~ b. Hence
G' = ({S, A, B}, {a, b}, r, S), where P' consists of S ~ aSA I bSB,
S ~ c, A ~ a, B ~ b is in GNP and is generating the given
language.
(b) The given language is generated by
G = ({S, A. B}, {a, b}, P, S), where P consists of
S ~ bA IaB, A ~ bAA Ias Ia. B ~ aBB IbS Ib. This itself is in GNP.
(c) The given language is generated by a grammar whose productions
are S ~ aAb. S ~ aA, A ~ aA, A ~ a, S ~ a, S ~ bB, B ~ b
and S ~ b. Of these productions we have to modify only one
production namely, S ~ aSb. This is done by replacing this