Problem Solving in Automata, Languages, and Complexity

3.2 Examples of Con text-Free Grammars^105

and Lz can be generated by

s:! + 1 IS21 1 OSzl.

Thus, we can combine the above rules to get a grarnmar G = ({S, Si, &},
(0, l}, R, S) that generates L, where

R = RI u R2 u {S + S1 I&}. cl

• Example 3.20 Find a context-free grammar generating

L = {z E {o,1} 1 x # ww for any w E (0, l}}.

SoZution 1. Let us analyze what types of strings are in L. I?irst, any string
x of an odd length belongs to L. Next, assume that 1x1 is even and x E L.
Write 2 = y1 y2... ynLz122. l l zm, where each yi or zj is a symbol in (0, 1).
Since x E L, yi # zi for some i = 1,2,. l l , nz. There are two cases.
Case 1. yi = 0 and zi = 1. Then, x looks like this:

x = y1 l ’ l yi-1 Oyi+l “*ymZl “‘Zi-1 lZi+l”‘Zfn.

\ - /k Y / \ /

j-J ,(m --i/l iL,(i -*l,\. t-t?. --,i

That is, x is of the form x = uOvlw for some 14, 21, w, satisfying 1211 = IuI+ IwI.

Case 2. ZJi = 1 and zi = 0. Similarly, x is of the form x = ~1vOw for some

U, v, w, satisfying Iv1 = IuI + Iwl.

In other words, we have L = Lo U L1 U L2, where

Ll = {UOVlW 1 u,v, w E {0,1}*, Iv1 = IUI + IWI},

L2 = {UlVOW 1 u, v,w E {0,1}*, 1211 = IUI + IWI},

L3 = {x ( 1x1 is odd}.

It is interesting to note that L1 is not disjoint from L2. That is, a string
x E L may belong to both L1 and L2. Furthermore, a string x in L1 may
be expressed as uOvlw by several different triples (u, v, w). But, this fact is
irrelevant. As long as L = L1 U L2 U L3, we can apply Theorem 3.17 to solve
this problem.
Now, it is easy to get grammars for languages L1, L2 and 1,s. For instance,
we can use the closure properties again: Define

x = {uov 1 u, v E {0,1}*, IUI = IVI},

Y = {ulv I 24, v E {0,1}*, 1241 = Ivl}.

Then, we have L1 = XY, L2 = YX and L3 = XUY. Let Gx = ({A},{O, l},
Rx, A), with
Rx = {A + 0 I OAO I OAl I 1AO I lAl},