1.1 Strings and Languages 5
1x1 many O’s, and so x E (0, 10}lXl C {O,lO}*. Suppose ~xf contains n > 1
occurrences of 1 ‘s. Then, each occurrknce of 1 in x must be followed by a 0,
for otherwise that symbol 1 is either followed by a 1 or is the last symbol of
x:, violating the assumption on X. So, we can write x as
0 l O(lO)O l o(lo)o‘o(lo)o***o,
where 0. l -0 means zero or more 0’s. Thus, x is the concatenation of strings
0 and 10, or, x E (0, lo}*. Cl
Example 1.6 Show that for any languages A and B,
(Au B)* = A* (BA*)*.Proof. We observe that every string in A (BA)* can be written as the
concatenation of strings in A U B. Indeed, a string x in A(BA)* must
be in A”(BA*)m f or some n, Y-J-~ - > 0. Thus, x can be decomposed into
x= X1X2” XnYlY2 “Yrn
where xl,... , xn E A and ~1,... , yrn E BA*. Similarly, each yj, j = 1,... , m.,
can be decomposed into
Ki = Yj,OYj,l Yj,2 l l ’ Yj,kj Ywith kj 2 0 and yj,o E B, yj,i,... , Yj,kj E A. Therefore,
x= x1x2 - l l xnYl,oY1,l l ’ l Yl,kI !h,o l l ’ y2,kz l ’ l $/m,k,
is the concatenation of strings in AU B. It follows that A (BA)* C (AU B)".
Next, we show that (A U B) C A(BA). To do so, consider a general
string x E (A U B)*. Again, we can see that x E (A U B)" for some n > - 0.
Thus, we may write
x= XlX2”‘Xn,
for some Xl,...,Xn E A U B. Now, assume that xil, xi2,... , xik E B, for
some k > 0 and 1 5 il < i2 <. l l < ik: 5 n, and the other strings xj, with
j # il, .I, ik, are in A. Then, we can write
where each yij E A. Thus, x E A(BA)” C - A(BA). It follows that
(A u B) C - A(BA).^0
Define the positive closure of a language A to be
A+ =A*A=AuA2uA3u-.