132 ~ Theory of Computer Science
G = ({S, SI. S:J, {a, b}, P, S) where P consists of
S ---+ S1 IS2
SI ---+ a IaSI ISl a IbSlSI ISl bS I IS1S1b
S2 ---+ b! bS 2 ! S2b IaS2S2 !S2aS2 ! SS2a.
G generates all strings over {a, b} having an unequal number of a's and b's.
EXAMPLE 4.24
If L 1 and L 2 are the subsets of {a, b} *, prove or disprove:
(a) If L 1 k L 2 and L l is not regular. then L 2 is not regular.
(b) If L I k L 2 and L 2 is not regular, then L l is not regular.
Solution
(a) Let L l = {aI/bIZ I n :2 I}. L l is not regular. Let L 2 = {a, b}*. By
Example 4.5, L 2 is regular. Hence (a) is not true.
(b) Let L 2 = {a"b" ! 11 :2 I}. It is not regular. But any finite subset is
regular. Taking L 1 to be a finite subset of L 2 , we disprove (b).
EXAMPLE 4.25
Show that the set of all non-palindromes over {a, b} is a context-free
language.
Solution
Let W E {a, b} * be a non-palindrome. Then w may have the same symbol in
the first and last places, same in the second place from the left and from the
right, etc.: this pattern will not be there after a particular stage. The
productions S ---+ aSa IbSb ! 1\ may be used for fulfilling the palindromecondition for the first and last few places. For violating the palindrome
condition, the productions of the form it ---+ aBb IbBa and B ---+ aB! bB I1\
will be usefuL So the required grammar is G = ({ S, it, B}, {a, b}, P, S)
where P consists of
S ---+ aSa IbSb IA
it ---+ aBb! bBa
B ---+ aB I bB ! 1\
SELF-TEST
Choose the correct answers to Questions 1-12:
1. For a grammar G with productions S ---+ SS, S ---+ aSb, S ---+ bSa, S ---+ 1\,
(al S ~ abba
(b) S :b abba
(c) abba EO L(G)
(d) S :b aaa