Question? Leave a message!




Finite Automata

Finite Automata
Finite AutomataOutline • Deterministic finite automata (DFA) – How a DFA works – How to construct a DFA • Nondeterministic finite automata (NFA) – How an NFA works – How to construct an NFA • Equivalence of DFA and NFA • Closure properties of the class of languages accepted by FA Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 2Finite Automata (FA) Finite set of states is in exactly one state at a time CONTROL Start state UNIT Final state(s) TAPE Move to the right one cell HEAD at a time INPUT TAPE Store input of the DFA Can be of any length Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 3What does an FA do • Read an input string from tape • Determine if the input string is in a language • Determine if the answer for the problem is “YES” or “NO” for the given input on the tape Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 4How does an FA work • At the beginning, – an FA is in the start state (initial state) – its tape head points at the first cell • For each move, FA – reads the symbol under its tape head – changes its state (according to the transition function) to the next state determined by the symbol read from the tape and its current state – move its tape head to the right one cell Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 5When does an FA stop working • When it reads all symbols on the tape • Then, it gives an answer if the input is in the specific language: – Answer “YES” if its last state is a final state – Answer “NO” if its last state is not a final state Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 6Example of a DFA 0 1 q a(q,a) 0 s s 0 s f s 1 f 1 Transition diagram f 0 f f 1 s Transition function Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 7How to define a DFA • a 5tuple (Q, , , s, F), where That’s why it’s called a finite automaton. – a set of states Q is a finite set – an alphabet  is a finite, nonempty set – a start state s in Q – a set of final states F contained in Q – a transition function  is a function Q  Q • See formal definition Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 8How an FA works 0 1 0 s f 1 Input: 001101 ACCEPT 0 0 1 1 0 1 REJECT Input: 01001 0 1 0 0 1 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 9Configurations Definition Let M =(Q, , , s, F ) be a deterministic finite automaton.  A configuration of M is an element of Q   Current state Unread input string 0 1 0 configurations of M (s, ), (s, 00), s f (s, 01101), (f, ), 1 (f, 0011011001), (f, 1111), (f, 011110) Transition diagram of M Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 10Yielding next configuration Definition • Let M = (Q, , , s, F ) be a deterministic finite automaton, and (q ,  ) and (q ,  ) be two configurations of M. 0 0 1 1 • We say (q ,  ) yields (q ,  ) in one step, denoted by (q ,  ) 0 0 1 1 0 0  (q ,  ), if (q , a) = q , and  =a  , for some a . M 1 1 0 1 0 1 • When a configuration yields another configuration, the first symbol of the string is read and discarded from the configuration. • Once a symbol in an input string is read, it does not effect how the DFA works in the future. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 11Example: yielding next configuration 0 1 0 (s, 001101)  (s, 01101) M s f  (s, 1101) M  (f, 101) M 1  (s, 01) M  (s, 1) M 0 0 1 1 0 1  (f, ) M Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 12Yield in zero step or more Definition • Let M = (Q, , , s, F) be a DFA, and (q ,  ) and 0 0 (q ,  ) be two configurations of M. (q ,  ) yields 1 1 0 0 (q ,  ) in zero step or more, denoted by (q ,  ) 1 1 0 0  (q ,  ), if M 1 1 – q = q and  =  , or 0 1 0 1 – (q ,  )  (q ,  ) and (q ,  )  (q ,  ) for 0 0 M 2 2 2 2 M 1 1 some q and  . 2 2 This definition is an inductive definition, and it is often used to prove properties of DFA’s. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 13Example: Yield in zero step or more 0 1 0 s f 1 (s, 01001) (s, 001101)  (f, 001)  (f, 101) M M  (f, 001)  (s, 01) M M  (f, 1) M  (f, ) M  (s, ) M  (f, ) M Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 14Accepting a string Definition • Let M = (Q, , , s, F) be a DFA, and   . We say M accepts  if (s, )  (f, ), when f M  F. Otherwise, we say M rejects . (s, 001101)  (f, )  M accepts 001101 M (s, 01001)  (s, )  M rejects 01001 M Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 15Language accepted by a DFA Let M = (Q, , , s, F ) be a DFA. The language accepted by M, denoted by L(M ) is the set of strings accepted by M. That is, L(M) = (s, )  (f, ) for some f  F M Example: • L(M) = x 0,1 the number of 1’s in x is odd. 0 1 0 s f 1 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 16Example 0 0, 1 0 0 1 1 0 s 0 1 1 0, 1 1 1 1 0 0 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 17How to construct a DFA • Determine what a DFA need to memorize in order to recognize strings in the language. – Hint: the property of the strings in the language • Determine how many states are required to memorize what we want. – final state(s) memorizes the property of the strings in the language. • Find out how the thing we memorize is changed once the next input symbol is read. – From this change, we get the transition function. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 18Constructing a DFA: Example • Consider L= 0,1 has both 00 and 11 as substrings. • Step 1: decide what a DFA need to memorize • Step 2: how many states do we need • Step 3: construct the transition diagram Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 19Example Got 00 Got 00 and 11 Got 00 as and got 1 as substrings substring 0 0, 1 0 Got 0 as substring 0 1 1 0 s 0 1 1 0, 1 1 1 Got nothing 1 0 0 Got 1 as substring Got 11 as Got 11 Got 11 and 00 substring and got 0 as substrings Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 20Constructing a DFA: Example • Consider L= 0,1  represents a binary number divisible by 3. – L = 0, 00, 11, 000, 011, 110, 0000, 0011, 0110, 1001, 00000, .... • Step 1: decide what a DFA need to memorize – remembering that the portion of the string that has been read so far is divisible by 3 • Step 2: how many states do we need – 2 states remembering that Choose this • the string that has been read is divisible by 3 Why • the string that has been read is indivisible by 3. – 3 states remembering that • the string that has been read is divisible by 3 • the string that has been read 1 is divisible by 3. • the string that has been read 2 is divisible by 3. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 21Using 2 states • Reading a string w representing a number divisible by 3. – Next symbol is 0. w 0, which is 2w, is also divisible by 3. • If w=9 is divisible by 3, so is 2w=18. – Next symbol is 1. w 1, which is 2w +1, may or may not be divisible by 3. • If 8 is indivisible by 3, so is 17. • If 4 is indivisible by 3, but 9 is divisible. • Using these two states is not sufficient. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 22Using 3 states • Each state remembers the remainder of the number divided by 3. • If the portion of the string that has been read so far, say w, represents the number whose remainder is 0 (or, 1, or 2), – If the next symbol is 0, what is the remainder of w 0 – If the next symbol is 1, what is the remainder of w 1 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 23How remainder changes Current Current Next New New number remainder symbol number remainder 3n 0 0 6n 0 3n 0 1 6n+1 1 3n+1 1 0 6n+2 2 3n+1 1 1 6n+3 0 3n+2 2 0 6n+4 1 3n+2 2 1 6n+5 2 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 24Transition table Current Current Next New Nex New t Current state state number remainder symbol number remainder 3n 0 0 6n 0 3n 0 1 6n+1 1 3n+1 1 0 6n+2 2 3n+1 1 1 6n+3 0 3n+2 2 0 6n+4 1 3n+2 2 1 6n+5 2 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 25Example DFA Current Next Next • M = (q , q , q , 0, 1, 0 1 2 state symbol state , q , q ) 0 0 q 0 q 0 0 0 q 0 q 1 q 0 1 1 q 0 q 1 1 2 1 q 1 q 0 1 0 q q 1 2 0 q 0 q 2 1 q 1 q 2 2 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 26Nondeterministic Finite Automata • Similar to DFA • Nondeterministic move – On reading an input symbol, the automaton can choose to make a transition to one of selected states. 0 0 – Without reading any symbol, the automaton can choose to make a transition to one of selected states or not.  Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 27How to define an NFA • a 5tuple (Q, , , s, F), where – a set of states Q is a finite set – an alphabet  is a finite, nonempty set – a start state s in Q – a set of final states F contained in Q Q – a transition function  is a function Q()2 • See formal definition Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 28Example of NFA  • An NFA accepting w0,1 w ends with 11 DFA 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0,1 1 1 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 29Yielding next configuration Definition • Let M = (Q, , , s, F) be a nondeterministic finite automaton, and (q ,  ) and (q ,  ) be two 1 1 0 0 configurations of M. • We say (q ,  ) yields (q ,  ) in one step, 0 0 1 1 denoted by (q ,  )  (q ,  ), if q (q , a,), 0 0 M 1 1 1 0 and  =a  , for some a . 0 1 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 30Yield in zero step or more Definition • Let M = (Q, , , s, F) be an NFA, and (q ,  ) 0 0 and (q ,  ) be two configurations of M. (q , 1 1 0  ) yields (q ,  ) in zero step or more, 0 1 1 denoted by (q ,  )  (q ,  ), if 0 0 M 1 1 – q = q and  =  , or Same as that for DFA 0 1 0 1 – (q ,  )  (q ,  ) and (q ,  )  (q , 0 0 M 2 2 2 2 M 1  ) for some q and  . 1 2 2 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 31Accepting a string Definition • Let M = (Q, , , s, F) be an NFA, and   . We say M accepts  if (s, )  (f, ), M when f  F. Otherwise, we say M rejects . Same as the definition for a DFA Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 32Language accepted by an NFA • Let M = (Q, , , s, F) be an NFA. • The language accepted by M, denoted by L(M) is the set of strings accepted by M. That is, L(M) =  (s,)  (f, ) for some M fF Same as the definition for a DFA Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 33How NFA’s work 0,1 1 1 (s,01111)  (s,1111)  (s,111) s q f  (s,11)  (s,1)  (s,) (s,01111)  (s,1111)  (s, 111) s, 01111  (s,11)  (s,1)  (q,) s, 1111 (s,01111)  (s, 1111)  (s, 111) s, 111 q, 111  (s,11)  (q,1)  (f, ) (s,01111)  (s, 1111)  (s, 111) s, 11 q, 11 f, 11  (q,11)  (f,1) s, 1 q, 1 f, 1 (s,01111)  (s, 1111)  (q, 111)  (f,11) f,  q,  s,  Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 34Other examples of NFA 0 0 0,1  • w 0,1 w has either 00 or 11 as substring 0,1 1 1  0,1 0 0 0,1 • w 0,1 w has 00 and 0,1  11 as substrings and 00 1 1 comes before 11 0,1 0,1 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 35DFA and NFA are equivalent M and M are equivalent  L(M ) = L(M ). d n d n DFA and NFA are equivalent  • For any DFA M , there exists an NFA M such that d n M and M are equivalent. (part 1) d n • For any NFA M , there exists a DFA M such that M n d d and M are equivalent. (part 2) n Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 36Part 1 of the equivalence proof • For any DFA M , there exists an NFA M such that d n M and M are equivalent. d n Proof: Let M be any DFA. We want to construct an d NFA M such that L(M ) = L(M ). n n d From the definitions of DFA and NFA, if M is a DFA then it is also an NFA. Then, we let M = M . n d Thus, L(M ) = L(M ). d n Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 37Part 2 of the equivalence proof • For any NFA M , there exists a DFA M such that n d M and M are equivalent. d n Proof: Let M = (Q, , , s, F) be any NFA. We want to n construct a DFA M such that L(M ) = L(M ). d d n First define the closure of q, denoted by E(q). Q Second, construct a DFA M =(2 , , ', E(s), F') d  Finally, prove  f  F (s,) (f, )  Mn  f 'F ' (E(s), ) (f ' , ). Md Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 38Eliminating transitions to multiple states 1 1 s q f 0,1 0 1 1 1 s s,q s,q,f 0 0 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 39Eliminating emptystring transitions 1ε 1 s p q 0 ε 0 ε 1 r f 1 s p,q, r 0 0 ,1 0,1 1 r p,q,r,f Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 40Closure of state q • Let M = (Q, , , s, F) be an NFA, and qQ. • The closure of q, denoted by E(q), is – the set of states which can be reached from q without reading any symbol. – pQ (q,) (p, ) M • If an NFA is in a state q, it can also be in any state in the closure of q without reading any input symbol. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 41Example of closure M=(s, q, f, a, b, c, , s, f) where  is defined below. state closure s q f s, q, f a b c q f q, f   s q f f f i j k L(M)=a b c i, j, k 0 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 42Another example of closure q q q q q 0 1 2 3 4 q 0 1 q q , q q 1 2 3 3 a  b 2 q , q 2 3 3  q q 1 2 q (q,a,r) (q,b,r) (q,,r) a b q q q 0 2 1  q q ,q q , q 1 0 4 2 3 a q q q q 3 4 2 4 q q 3 4  q q 4 3 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 43Constructing the equivalent DFA Let M = (Q, , , s, F) be any NFA. We construct a n Q DFA M =(2 , , ', E(s), F'), where : d –'(q',a) =  rE(p) p (q,a) and qq' – F' = f  Q f F ) DFA ε p r a ε q a ε Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 44Example of DFA construction q 0 E(q ) E(q ) E(q ) E(q ) E(q ) a 0 1 2 3 4  b q , q , q , q , q q q ,q 0 1 1 2 2 3 3 4  q q 1 2 q , q q 2 3 3 a b  a q q 3 4  Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 45Example of DFA construction q ,q ,q ,q 0 1 2 3 E(q ) E(q ) E(q ) E(q ) E(q ) 0 1 2 3 4 a q , q , q , q q q ,q 0 1 1 2 3 3 4 a q , q q , q 2 3 2 3 q ,q ,q ,q ,q 0 1 2 3 4 b  (q,a,r) (q,b,r) (q,,r) b q q q a 0 2 1 q q q q q a 1 0 4 2 3 q ,q ,q q ,q 2 3 4 3 4 b q q 2 4 b q q a,b 3 4 q q 4 3  Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 46Prove property of  and ' Q Let M = (Q, , , s, F) be any NFA, and M = (2 , , ', n d E(s), F') be a DFA, where –'(q', a) =  rE(p) p (q,a) and qq' – F' = f  Q f F   Prove  ,  fF (s,) (f, )  f 'F ' (E(s), ) Mn (f', ) and ff' by induction. Md  Prove a more general statement  ,  p, qQ (p,) (q, )  (E(p), ) (q', ) and qq'. Mn Md Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 47Proof Part I: For any string  in Σ, and states q and r in Q, there exists R Q such that (q, )  (r, ε)  (E(q), )  (R, ε) and Mn Md rR. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 48Proof Basis: Let  be a string in Σ, q and r be states in Q, and (q, )  (r, ε) in 0 step. Mn Because (q, )  (r, ε) in 0 step, we know (1) q=r , Mn and (2) =ε. Then, (E(q), ) = (E(r), ε). Thus, (E(q), )  (E(r), ε) . Md That is, there exists R=E(r) such that r R and (E(q),)  (R, ε). Md Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 49Proof Induction hypothesis: For any nonnegative integer k, string  in Σ, and states q and r in Q, there exists R Q: (q, )  (r, ε) in k steps (E(q), )  (R, ε) and Mn Md rR. Induction step: Prove, for any nonnegative integer k, string  in Σ, and states q and r in Q, there exists R Q: (q, )  (r, ε) in k+1 steps (E(q), )  (R, ε) Mn Md and rR. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 50Proof Let  be a string in Σ, q and r be states in Q, and (q, )  (r, ε) in k+1 steps. Mn Because (q, )  (r, ε) in k+1 steps and k0, Mn there exists a state p in Q and a string Σ such that (q, )  (p, a) in k steps and (p, a) Mn  (r, ε) for some a Σε. Mn Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 51Proof From the induction hypothesis and (q, )  (p, a) in Mn k steps, we know that there exists PQ such that (E(q), )  (P, a) and pP. Md Since (p, a)  (r, ε), r (p, a). Mn From the definition of  of M , E((p, a))  (P, a) d because pP. Because r (p, a) and E((p, a))  (P, a), r(P, a). Then, for R=(P, a), (P, a)  (R, ε) and rR. Md Thus, (E(q), )  (P, a)  (R, ε) and rR. Md Md Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 52Proof Part II: For any string  in Σ, and states q and r in Q, there exists R Q such that rR and (E(q), )  (R, ε) (q, )  (r, ε). Md Mn R E(q) rR r q Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 53Proof Basis: Let  be a string in Σ, q and r be states in Q, R be a subset of Q such that r R and (E(q), )  (R, ε) Md in 0 step. Because (E(q),)  (R, ε) in 0 step, E(q)=R and =ε. Md From the definition of E, (q, ε)=R because E(q)=R. Then, for any rR, (q, )  (r, ε). Mn That is, there exists R=E(q) such that r R and (q, )  (r, ε). Mn Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 54Proof Induction hypothesis: For any nonnegative integer k, string  in Σ, and states q and r in Q, there exists R Q such that rR and: (E(q), )  (R, ε) in k steps (q, )  (r, ε). Md Mn Induction step: Prove, for any nonnegative integer k, string  in Σ, and states q and r in Q, there exists R Q such that rR: (E(q),) (R, ε) in k+1 steps (q, )  (r, ε). Md Mn Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 55Proof Let  be a string in Σ, q and r be states in Q, and (E(q), )  Md (R, ε) in k+1 steps. Because (E(q), )  (R, ε) in k+1 steps and k0, there exists Md Q P2 (i.e. PQ) and a string Σ such that =a, (E(q), )  (P,ε) in k steps and (P, a)  (R, ε) for some aΣ. Md Md a P R k+1 steps E(q) rR r q Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 56Proof From the induction hypothesis and (E(q), )  (P,ε) in k Md steps, we know that there exists pP such that (q, ) (p,ε) Mn (i.e. (q, a)  (p, a) ). Mn Since (P, a)  (R, ε), there exists rR such that r=(p, a). Md Then, for some rR, (p, a)  (r, ε). Mn Thus, (q, )  (p, a)  (r, ε) for some rR. Mn Mn a P R k+1 steps E(q) pP a p r rR q Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 57Closure Properties • The class of languages accepted by FA’s is closed under the operations – Union – Concatenation – Complementation – Kleene’s star – Intersection Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 58Closure Property under Union The class of languages accepted by FA is closed under union. Proof: s Let M = (Q , Σ,  , s , F ) and A A A A A A ε M = (Q , Σ,  , s , F ) be any FA. B B B B B s We construct an NFA M = ε (Q, Σ,, s, F) such that s B – Q = Q Q s A B – =  (s, ε, s , s ) A A A B – F = F F A B We prove that L(M) = L(M )L(M ). A B Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 59Proof To prove L(M) = L(M ) L(M ), we prove: A B I. For any string Σ L(M ) or L(M ) L(M) A B II. For any string Σ L(M ) and L(M ). L(M) A B For I, consider (a) L(M ) or (b) L(M ). A B For (a), let L(M ). A From the definition of strings accepted by an FA, there is a state f in F such that (s , ) (f , ε). A A A MA A Because , (s , ) (f , ε) also. A A M A s A Because s (s,ε), (s, ) (s , ). A M A ε Thus, (s, ) (s , ) (f , ε). M A M A s Because f F, L(M). ε A s Similarly for (b). B Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 60Proof For (II), let L(M )L(M ). A B Because (s, ε, s , s ) , either (s,) (s ,) or (s, ) (s , ) only. A B M A M B Because L(M ), there exists no f in F such that (s ,) (f ,ε). A A A A MA A Because L(M ), there exists no f in F such that (s , ) (f , ε). B B B B MB B Since there is no transition between states in Q and Q in M, there A B exists no state f in F=FF such that (s, ) (s , ) (f , ε) A B M A M A or (s, ) (s , ) (f , ε). M B M B That is, L(M). s A ε Thus, L(M) = L(M )L(M ). A B s ε s B Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 61Closure under concatenation ε ε s s A B ε M B M A Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 62Closure under complementation s A M A DFA only Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 63Closure under Kleene’s star   s s f f A A  Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 64Closure under intersection The class of languages accepted by FA is closed under intersection. Proof: Let L and L be languages accepted by FA. 1 2 L L = (LL ) 1 2 1 2 By the closure property under complementation, there are FA acceptingL andL . 1 2 By the closure property under union, there is an FA acceptingL 1 L . 2 By the closure property under complementation, there is an FA accepting(LL ). 1 2 Thus, the class of languages accepted by FA is closed under intersection. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 65DFA accepting the intersection of two languages Let M = (Q , Σ,  , s , F ) and A A A A A M = (Q , Σ,  , s , F ) be any FA. B B B B B We construct an NFA M = (Q, Σ, , s, F) such that – Q = Q Q A B – =  (i.e. ((q ,q ),a) =  (q ,a) (q ,a)) A A A B A A B B – s = (s , s ) A B – F = F F A B Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 660 Example 0 p ,q 0 0 1 1 q 0 1 p ,q 1 1 1 0 p ,q 1 0 1 1 1 0 0 1 p ,q 0 2 p ,q q q 2 0 1 2 0 1 1 p ,q 1 0 1 p ,q 1 2 0,1 1 1 1 p p p 0 1 2 p ,q 2 1 p ,q 2 2 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 67Check list Basic Advanced  Explain how DFA/NFA work  Prove DFA/NFA accepting a (configuration, yield next language configuration)  Prove properties of DFA/NFA  Find the language accepted by  Configuration change DFA/NFA  Under some modification  Construct DFA/NFA accepting a  etc. given language  Prove some properties of  Find closure of a state languages accepted by  Convert an NFA into a DFA DFA/NFA  Prove a language accepted by FA  Under some modification  Construct FA from other FA’s  Surprise Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 68
Website URL
Comment