Chapter 6: Context-Free Languages ,i;l, 219
So ababbab E L(G).
S ~ A 2 aAbA 2 (as in the derivation of the first string)
~ aaaabaa
S ~ A
2 aAbA
2
~ bbabbbb
So ababbab, aaaabaa, bbabbbb are in L(G).
(c) S ~ ASA. If B ~ 11', then 11' starts with a and ends in b or vice versa
and I ,v I 2' : 3. If aaa is in L( G), then the first two steps in the
derivation of aaa should be S ~ ASA ~ ABA or S ~ aBa. The
length of the terminal string thus derived is of length 5 or more.
Hence aaa 9!: L(G). A similar argument shows that bbb 9!: L(G).
S ~ B ~ acb ~ aAb ~ abb. So abb E L(G)
(d) False. since the single-step derivations starting with C can only be
C ~ ACA or C ~ A.
(e) C ~ ACA ~ AAA ~ bab. True
(f) Let 11' = abab. If C ~ 11', then C ~ ACA ~ 11' or C ~ A ~ 11'.
In the first case 111'1 = 3, 5. 7..... As 111'1 = 4. and A ~ 11' if and
only if 11' = a or b, the second case does not arise. Hence (f) is false.
(g) C ~ ACA ~ AAA. Hence C ~ AAA is true.
(h) A 9!: L(G).
EXAM PLE 6.21
If G consists of the productions S ~ aSa IbSb I aSb I bSa I A, show that L(G)
is a regular set.
Solution
First of all, we show that L(G) consists of the set L of all strings over {a, b}.
of even length. It is easy to see that L(G) I: L. Consider a string 11' of even
length. Then, 11' = aja2 ... a2n-Ia2n where each ai is either a or b. Hence
S ~ a 1 Sa2n ~ aja2Sa211_ja2n ~ aja2 ... a l1 Sa n +j ... a2n ~ a1 a2 ... a21]'
Hence L I: L(G).
Next we prove that L = L(G 1 ) for some regular grammar G j • Define
G 1 = ({S, Sl' S2' S3' S4}. {a, b}. P, S) where P consists of S ~ aSj, Sl ~ as,
S ~ aS2, S2 ~ bS, S ~ bS 3 • S3 ~ bS, S ~ bS 4 • S4 ~ as, S ~ A.
Then S :b aja2S where a1 = a or band a2 = a or b. It is easy to see that
L(G 1 ) = L. As G j is regular, L(G) = L(G j ) is a regular set.
EXAMPLE 6.22
Reduce the following grammar to CNF:
S ~ ASA IbA. A ~ BIS,
B~c
So ababbab E L(G).
S ~ A 2 aAbA 2 (as in the derivation of the first string)
~ aaaabaa
S ~ A
2 aAbA
2
~ bbabbbb
So ababbab, aaaabaa, bbabbbb are in L(G).
(c) S ~ ASA. If B ~ 11', then 11' starts with a and ends in b or vice versa
and I ,v I 2' : 3. If aaa is in L( G), then the first two steps in the
derivation of aaa should be S ~ ASA ~ ABA or S ~ aBa. The
length of the terminal string thus derived is of length 5 or more.
Hence aaa 9!: L(G). A similar argument shows that bbb 9!: L(G).
S ~ B ~ acb ~ aAb ~ abb. So abb E L(G)
(d) False. since the single-step derivations starting with C can only be
C ~ ACA or C ~ A.
(e) C ~ ACA ~ AAA ~ bab. True
(f) Let 11' = abab. If C ~ 11', then C ~ ACA ~ 11' or C ~ A ~ 11'.
In the first case 111'1 = 3, 5. 7..... As 111'1 = 4. and A ~ 11' if and
only if 11' = a or b, the second case does not arise. Hence (f) is false.
(g) C ~ ACA ~ AAA. Hence C ~ AAA is true.
(h) A 9!: L(G).
EXAM PLE 6.21
If G consists of the productions S ~ aSa IbSb I aSb I bSa I A, show that L(G)
is a regular set.
Solution
First of all, we show that L(G) consists of the set L of all strings over {a, b}.
of even length. It is easy to see that L(G) I: L. Consider a string 11' of even
length. Then, 11' = aja2 ... a2n-Ia2n where each ai is either a or b. Hence
S ~ a 1 Sa2n ~ aja2Sa211_ja2n ~ aja2 ... a l1 Sa n +j ... a2n ~ a1 a2 ... a21]'
Hence L I: L(G).
Next we prove that L = L(G 1 ) for some regular grammar G j • Define
G 1 = ({S, Sl' S2' S3' S4}. {a, b}. P, S) where P consists of S ~ aSj, Sl ~ as,
S ~ aS2, S2 ~ bS, S ~ bS 3 • S3 ~ bS, S ~ bS 4 • S4 ~ as, S ~ A.
Then S :b aja2S where a1 = a or band a2 = a or b. It is easy to see that
L(G 1 ) = L. As G j is regular, L(G) = L(G j ) is a regular set.
EXAMPLE 6.22
Reduce the following grammar to CNF:
S ~ ASA IbA. A ~ BIS,
B~c