Problem Solving in Automata, Languages, and Complexity

1.1 Strings and Languages 7

Proof. We apply Arden’s lemma to the second equation, and we get B =
{b} l {E} = {!I}. Th en, we apply Arden’s lemma to the first equation, and
we get
A = {a}*({~} u {b}B).

Now, substitute {b}” for B, we have

A = {a}({~} u {b}(b)) = {a}(b). 0

Exercise 1.1

1. Let A = {grand, E} and B = {mother, father}. What are AB and

A*B?

2. Let A be a language over {a, b} and IX: E {a, b}*. Find necessary and

sufficient conditions in terms of x and A for the equation

A* - (23 = A+.

3. For each of the following equations, determine whether it is true for all

languages A, B or not. Present a proof or a counterexample.

(a) (AR) = (A)R.

(b) (A+) = A.

(c) (A uAR)* = A* u (A*)R.

(d) A2uB2 =(AuB)2.

(e) A n B = (A n B)*.

4. (a) Show that, for k > 1, UfL-,Ai = ({E} UA)".

(b) Show that, for n > 1, (A)” = A.

(c) Assume that E @A. Show that, for n > - 1, (A+)” = AnA*.

5. Prove the following identities on languages A, B, C, D:

(a) A(BA) = (AB)A.

(b) (A u B)” = (A* B*)*.

(c) A(B u C) = AB u AC.

(d) (A u B)C = AC u BC.

(e) AB(DABUC) = (AUBCD)BC.

6. Find the shortest string over alphabet (0) which is not in {E, 0, 02, 05}3

* 7. Find the general solutions for the equation

xy= yx

for x, y E {O,l}*.