Problem Solving in Automata, Languages, and Complexity

22

( > C

2. (4

(b)

3. Find
   .

REGULAR LANGUAGES

((00 + ll)* + (OOl+ 11o)*)*.

Find an algorithm to find a shortest string in a regular set with a

given regular expression.

Find an algorithm to find a shortest string in a regular set with a

given graph representation of a regular expression.

labeled digraph representations for the following regular expres-

sions:

(a) (00 + lO)(lOl)* + 01.

(b) ((00 + ll)* + (001 + llO)*)*.

(c) (a + bc*d)*bc*.

4. Determine the regular expressions represented by digraphs in Figure 1.7.

b

Figure 1.7: Three digraphs for Exercise 4.

5. Find the simplest digraph representing &.

* 6. Find counterexamples to show that Theorem 1.25 is incorrect if we re-

move the requirements that u must be a nonfinal vertex and v must be

a noninitial vertex.