Problem Solving in Automata, Languages, and Complexity

66 FINITE AUTOMATA Figure 2.44: A DFA over a singleton alphabet has exactly one cycle. Proof. We prove this result in four steps ...

2.6 Closure Properties of Regular Languages 67 alphabets C and F. We observe that C(A, B) = A n C(C, B). From the third case, we ...

68 (b) {x 1 x E A,xx E A}. FINITE AUTOMATA (c) A, = {y 1 xy E A}, where x is a fixed string. (d) (w2 l l ’ a271^1 a2ala4a3 l l ~ ...

2.7 Minimum Deterministic Finite Automata 69 (d) If A and AB are regular, then B is regular. (e) If A and B are regular, then Up ...

70 FINITE AUTOMATA 2n2 + 2 states. If we convert this NFA to an equivalent DFA, the new DFA would have, in the worst case, 20cn2 ...

2.7 Minimum Deterministic Finite Automata 71 symbol, Z.XN E L e yw E L for all w E (0 + l)+. Moreover, since x and y also end wi ...

72 FINKCE AUTOMATA * q2 Figure 2.45: Computation path of a string 20. By a simple induction, we can extend this property to J([E ...

2.7 Minimum Deterministic Finite Automata 73 Figure 2.46: Solution to Example 2.51. Example 2.51 Find the minimum DFA for langua ...

74 FINITE AUTOMATA Example 2.52 Construct the minimum DFA for language (0 + l)*O(O + 1)“. Solution. This language L contains all ...

2.7 Minimum Deterministic Finite Automata 75 shows that, although NFA’s and DFA’s have the same computational power for recogniz ...

(^76) FINITE AUTOMATA Figure Figure 2.47: 2.47: DFA DFA AL AL d Figure 2.48: Graph G. qo 41 42 43 % Figure 2.50: The table build ...

2.7 Minimum Deterministic Finite Automata 77 (^0 0 1) O L-2 1 X 0 1 0 c) u (^0) 0, 1 Y 0 1 0 0 1 b 1 0 (^0) 0, f 0 0 ------e---- ...

78 FINITE AUTOMATA is not regular. Example 2.54 Show that the following language is not regular: L = {XP I x E {O,l)‘)* Proof. F ...

2.7 Minimum Deterministic Finite Automata 79 Exercise 2.7 Find all equivalence classess of RL for the following languages: (a) ...

80 FINITE AUTOMATA Figure 2.53: An NFA for Exercise 5. 2.8 Pumping Lemmas Not all languages are regular. In fact, there are unco ...

2.8 Pumping Lemmas 81 also have uv*w C L. (E.g., uv2w is in L because S(qo,uv2w) = J(qi,vvw) = @Ii f VW) = qqiG) = !-If 0) cl No ...

82 F1NKCE AUTOMATA V y = uvw Figure 2.55: The path (q~,~,q~,.,q,=~.,q,~,q~,~,f)~ Example 2.60 (0” In 1 n > 0) - is not a regu ...

2.8 Pumping Lemmas 83 string a = 0”110” E L, and let II: = E, y = OS, and x = 110”. By the pumping lemma, y can be written as y ...

84 FINITE AUTOMATA any Ic > 0, zuvkw is in L. Take k = 0. We get xuw = O1OS+llOs+llOt, with 1 < - t <s. - Since t $ l(s ...

2.8 Pumping Lemmas 85 Proof. Assume, by way of contradiction, that L is regular and is accepted by a DFA M of s > 0 states. C ...