Problem Solving in Automata, Languages, and Complexity

REGULAR LANGUAGES

Intersection

A\B A-B

Substrac tion

Figure 1.1: Set operations.

(c) Let A = {(Ol)n 1 n > - 0) and B = (01,010). Then,

AB = {(Ol)n, (Ol)nO 1 n > - 1)

ABA = {(Ol)n 1 n > - l} U {(Ol)nO(O1)m 1 m. > - 0, n > - 1). cl

For any language A, we define A1 = A, A2 = AA, and A’” = AAkS1 for
k > 2. We also define A0 = {E}. (Note that 8 and {E} are two different

languages: Q)A = 8 and {E}A = A(E) = A.) For example, for C = (0, l},

we have C2 = {OO,Ol, 10, 11} and, in general, for k > 0, Ck is the set of all
strings of length k over C. Therefore, C* = Co U C1 UC2 U l l l. The following
is the more general star operation based on this formula:

KZeene closure (or star closure): For any language A, define

A* = A”uA1uA2u-.

• 
  
  
  
  • {w I w is the concatenation of 0 or more strings from A}.
  
  
  
  

Example 1.5 The Zanguuge {O,lO}* is the set of all binary strings having no
substring 11 and ending with 0.

Proof. It is clear that the concatenation of any number of 0 and 10 must end
with 0. Furthermore, it cannot produce a substring 11, since the ending O’s
of both strings 0 and 10 separate any two l’s in the concatenated string.
Conversely, let z be a string over (0, 1) h aving no substring^11 and ending
with 0. If x contains no occurrence of 1, then x is the concatenation of