Problem Solving in Automata, Languages, and Complexity

46 FINITE AUTOMATA (a) NFA Ml' (b) NFA M2' Figure 2.28: Two attempts for Kleene closures of NFA’s. To see how to do this convers ...

2.4 Converting an NFA to a DFA 47 0 a Figure 2.29: Converting an NFA to a DFA. Solution. We construct the DFA M’ as follows: Ste ...

48 FINITE AUTOMATA Solzstion. Following the above procedure, we obtain the following table for the transition function S’ of the ...

2.4 Converting an NFA to a DFA 49 Qc = {P) Qo = GLS) QI = {q} Qoo = { 1 r QOI = {P,w) QII = (Q,r) Qooo = {s} Qolo = is r, 4 QIIO ...

50 FINITE AUTOMATA Figure 2.31: Solution to Example 2.27. and 6’ is defined by w7’, 0) = {Qo, Ql) u { qi+l 1 qi E q’ and 1 < ...

2.4 Converting an NFA to a DFA 51 a, c (a) C 8 a, c m Figure 2.32: Two NFA’s for Example 2.28. Next, we define Q’ = {qa, qb, qC, ...

52 FINITE AUTOMATA 6” %a qsb 4sc 4aa qab Qac @a qbb qbc 4ca qcb 4cc ro41 b 140 > (qbd {A ab b&f, qbc) bIba} {%a~ qac) {qb ...

2.5 Finite Automata and Regular Expressions 53 (b) The set of all binary strings ending with 00 or 01 or 10. (c) The set of bina ...

(^54) FINITE AUTOMATA Figure 2.34: Solution to Example 2.29. Figure 2.35: Solution to Example 2.30. Example 2.30 Construct an NF ...

2.5 Finite Automata and Regular Expressions 55 8 a+b Figure 2.36: Multiple edges can be removed. d (1) (2) Figure 2.37: Basis st ...

56 FINITE AUTOMATA Figure 2.38: Induction step. +1> = a% for some il >^0 and, for j = 2,... , k, +Q) is either c or d& ...

2.5 Finite Automata and Regular Expressions 57 Figure 2.39: NFA with a single final state. Theorem 2.31 Let L be a language. The ...

58 FINITE AUTOMATA O+l^0 O+l 01 Figure 2.40: Finding a regular expression from an NFA. Figure 2.41: An NFA accepting O*. For ea ...

2.6 Closure Properties of Regular Languages 59 (4 W Figure 2.42: Two NFA’s for Exercise 4. result provides us with useful tools ...

60 FIN..TE AUTOMATA Lo. Finally, we use the method of Section 2.5 to construct an NFA M’ such that L(W) = L(s). This process, ho ...

2.6 Closure Properties of Regular Languages 61 Proof. Let r be a regular expression for language L and, for each a E C, ra be th ...

62 FINITE AUTOMATA Example 2.38 Prove that if L is regular, so is MIN(L). Proof. Assume that A4 = (Q, C,S, q, F) is a DFA which ...

2.6 Closure Properties of Regular Languages 63 Figure 2.43: Solution to Example 2.40. For each states of M, we make two cojes of ...

(^64) FINITE AUTOMATA (3) We accept (I: if the two parallel simulations of step (2) end at a same state Q~C (which is not requir ...

2.6 Closure Properties of Regular Languages 65 Proof. We use the second proof technique of the last example to solve this proble ...