Problem Solving in Automata, Languages, and Complexity

1.2 Regular Languages 15

Proof. We prove it by induction.
Basis Step (1): The empty set 8 has a regular expression 8 in disjunctive
normal form.
Basis Step (2): F or any symbol a, {a) has a regular expression a in dis-
junctive normal form.
Induction Step (3): Suppose that language L1 has a regular expression

a1 + a2 + l l. + am in disjunctive normal form and language L2 has a regular

expression pr + p2 + l l l + & in disjunctive normal form. Then,

(a) L1 U L2 has a regular expression al + l l. + a, + PI + l l. + ,&.

(b) LlL2 has a regular expression (Cr=, ~i)(xy=, pj> = CF1 - c,“-, - ai@j.

(c) L; has a regular expression (EL, ai) = (c+z. l oak) (cf. Exercise

5(b) of Section 1.1).

Thus, L1 U L2, L1 L2, and Lf all can be represented by regular expressions in

disjunctive normal form. This completes the induction proof.^0

Exercise 1.2

1. Describe in English the languages expressed by the following regular
   expressions:

(a) (0* l*)*O.

(b) (Ol*)*O.

(c) (00 + 11 + (01 + lO)(OO + ll)*(ol + lo))*.

(d) 0* + (O*l+ O*ll)(O+l + O+ll)*O*.

2. Simplify the following regular expressions:
   (a) (OO)O + (OO).
   (b) (0 + l)(~ + OO)+ + (0 + 1).
   (c) (0 + E)O”l.


3. Construct regular expressions for the following languages over alphabet
   (0, 1):
   (a) Th e se t o f a 11 t s rin g s whose fifth symbol from right is 0.
   (b) The set of all strings having either 000 or 111 as a substring.
   (c) The set of all strings having neither 000 nor 111 as a substring.
   (d) The set of all strings having no substring 010.
   (e) The set of all strings having an odd number of 0’s.
   (f) The set of all strings having an even number of occurrences of
   substring 011. [Hint: First find the regular expression for the set
   of binary strings having no substring 011.1


4. Show that (02 + 03) = (020)*.