Problem Solving in Automata, Languages, and Complexity

6 REGULAR LANGUAGES Example 1.7 A+ = A* if and only if 6 E A. Proof. Clearly, A+ - C A*. If & E A, then {E} = A0 C - A C - A ...

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 app ...

8 * 8. Solve the following language equations for A = {a)Cu {b}B, B= 14 u WAU C = {E} u{a)A. REGULAR LANGUAGES languages A, ...

1.2 Regular Languages 9 To further reduce the number of parentheses in a regular expression, we apply the following preference r ...

10 REGULAR LANGUAGES Example 1.14 Find integers which a re the a regula r expression for the set of binary expansions of of4. So ...

1.2 Regular Languages 11 (For convenience, we added E to each case. Note that & is in B.) Now, we can combine cases (1) (a), ...

12 REGULAR LANGUAGES a3 = 3). Also, for k = 0, 1,... , 9, let Lk be the set of all nonempty strings over {ao,... , ak} having no ...

1.2 Regular Languages 13 If the second rightmost symbol is the first case, then the two rightmost symbols form a minimal string ...

14 REGULAR LANGUAGES = {w 1 (3u)[uw E Ll]} u {w 1 (3u)[uw E L21) = L1’ u L2’. (b) (L1L2)’ = {w 1 (~U)[UW E ~51~521) = {w ] eithe ...

1.2 Regular Languages 15 Proof. We prove it by induction. Basis Step (1): The empty set 8 has a regular expression 8 in disjunct ...

16 REGULAR LANGUAGES Construct a regular expression for the set of all strings over alphabet {( $( i)( a)*( !J( a);( i)( i+( i ...

1.3 Graph Representations 17 Figure 1.2: A digraph. In some applications, we would like to assign labels to edges of a digraph. ...

REGULAR LANGUAGES Figure 1.3: Graph G(r) for regular expression r. S: z E L(r) if and only if there is a path (~1, ~12,.... ?.&a ...

1.3 Graph Representations 19 Figure 1.4: Labeled digraph G(r) for T = (11 + O)*(OO + l)*. Theorem 1.25 Let r be a regular expre ...

20 REGULAR LANGUAGES ;!i 0 E -@ 0 0 1 1 0 0 0 0 Figure 1.5: Simpler solution for Example 1.24. with label E. The shrinking of (u ...

1.3 Graph Represen t a tions 21 a *b(c+da *b) * b Figure 1.6: Labeled digraph G(r) for Y = ab(c + dab)*. In fact, if an E-edge i ...

22 ( > C (4 (b) Find . REGULAR LANGUAGES ((00 + ll)* + (OOl+ 11o)*)*. Find an algorithm to find a shortest string in a re ...

Finite Automata 2.1 Deterministic Finite Automata In this section, we introduce a simple machine model, called deterministic fin ...

24 FINKI- AUTOMATA finite Figure 2.1: A finite automaton. of states: an initial stute 40 at which the DFA begins to work, and a ...

2.1 Deterministic Finite Automata 25 Figure 2.2: The transition diagram of the DFA of Example 2.1. Since the transition function ...