Problem Solving in Automata, Languages, and Complexity

26 FINITE AUTOMATA Figure 2.3: DFA of Example 2.4. will accept the input string. (We call such a state a success state.) From th ...

2.1 Deterministic Finite Automata 27 Figure 2.4: DFA of Example 2.5. then comes back to ~0, it must have read five l’s, with an ...

28 FINITE AUTOMATA 0 a 0 C Figure 2.6: Three DFA’s of Exercise 3. (b) Suppose n = 7, d = 2, a0 = 0 and al = 1. Find 6(qs,OlOl) a ...

2.2 Examples of DFA ‘s^29 0 x3 0 1 0 a Figure 2.7: DFA for (0 + l)*. 0 a 09 Figure 2.8: Solution to Example 2.7. one edge and pu ...

30 FINITE AUTOMATA 0 a 0 C Figure 2.9: Solution to Example 2.8. Suppose that the string ~1~2 •GC~ is stored on the tape, where e ...

2.2 Examples of DFA ‘s 31 (c) -E3+ 0 O - 1 O 8 2 l (^1 1 0) Figure 2.10: Solution to Example 2.9. Intuitively, for each i = 0, 1 ...

32 FINITE AUTOMATA 0 a 04 9 Figure 2.11: Solution to Example 2.10. At state q2, if we read more input symbols, then we need to f ...

2.2 Examples of DFA ‘s 33 Figure 2.12: DFA for Example 2.11. Figure 2.13: DFA for set (11. Au 4, with leading zeros allowed. Usi ...

34 FIN.TE AUTOMATA Figure 2.14: Product DFA for Example 2.12. For instance, the computation path of x = 0101 in this product aut ...

2.2 Examples of DFA ‘s 35 0 a 0 C Figure 2.15: The second solution to Example 2.13. Solution 2. We can also use the checker meth ...

36 FINITE AUTOMATA the sum of n1 and n2. So, this method saves some states. It, however, needs some heuristics to determine the ...

2.2 Examples of DFA ‘s 37 Figure Figure 2.16: 2.16: Solution Solution to to Example Example 2.15. 2.15. (d) ( e > (f ) Cd o-4 ...

38 FINITE AUTOMATA (b) The set of Example 2.14. (c) The set of Exercise 2(a) above. (d) The set of Exercise 2(c) above. 2.3 Nond ...

2.3 Nondeterministic Finite Automata 39 Figure 2.17: The transition diagram of an NFA. three computation paths: Note that in the ...

40 FINITE AUTOMATA For instance, in the above example, ~-closure({!lo)> = {Qo, Ql}, ~-closure({qa}) = {Ql, 42}* Now, we exten ...

2.3 Nondeterministic Finite Automata 41 ‘b 1 0 g- / \ (^0) (I- 1 1 0 -? (reject) q’,Yqo (^0) O-4 1 (reject) (reject) (accept) Fi ...

42 FINITE AUTOMATA Solution. Figure 2.22: The Solution to Example 2.19. We use the E-moves to connect three simple NFA’s into on ...

2.3 Nondeterministic Finite Automata 43 (a) (b) 0 (^0 0) 1 1 1 1 1 ? t t? 7 0 0 0 (^1 1 1 1 1) 0 0 0 0 0 0 0 0 0 Figure 2.23: So ...

44 FINITE AUTOMATA Figure 2.25: Kleene closure of an NFA. final state f ( so that the empty string E is accepted). This NFA IV i ...

2.4 Converting an NFA to a DFA 45 0 a (b) 0 C Figure 2.27: Three NFA’s of Exercise 2, (c) The set of binary strings that contain ...