sectnfaH.pdf

CPS 140 - Mathematical Foundations of CS Dr. Susan Rodger Section: Finite Automata #28Ch. 2#29 #28handout#29 Deterministic Finite Accepter #28or Automata#29 #28Read Ch. 2.1-2.2#29 ADFA=#28K,#06,#0E,q 0 ,F#29 head moves input tape tape head current state aab bab 01 where K is #0Cnite set of states #06 is tape #28input#29 alphabet q 0 is initial state F #12 K is set of #0Cnal states. #0E:K#02#06!K Example: Create a DFA that accepts even binary numbers. Transition Diagram: #1A#19 #1B#18 #1A#19 #1B#18 #12#11 #13#10 #08 #08 #08 #08 P P P Pq ! ! ! X X X X Xy - T T T #1A #1A J J #03 #03 #03#0F T T T #1A #1A J J #03 #03 #03#0F 01 q1q0 1 0 M=#28K,#06,#0E,q 0 ,F#29 = Tabular Format 0 1 q0 q1 q0 q1 q1 q0 Example of a move: #0E#28q0,1#29= 1 Algorithm for DFA: Start in start state with input on tape q = current state s = current symbol on tape while #28s != blank#29 do q=#0E#28q,s#29 s = next symbol to the right on tape if q2F then accept Example of a trace: 11010 Pictorial Example of a trace: 100 q0 q1 100 q0 q1 100 q0 q1 1) 3) 2) 4) 100 q0 q1 De#0Cnition: Con#0Cguration: elementofK#02#06 #03 Movebetween con#0Cgurations: ` Movebetween several con#0Cgurations: `#03 Examples #28from prev FA#29: De#0Cnition The language accepted byaDFA M=#28K,#06,#0E,q 0 ,F#29 is set of all strings on #06 accepted byM. Formally, L#28M#29=fw 2 #06 #03 j #28q 0 ;w#29`#03#28p;#0F#29;p2Fg 2 Trap State Example: L#28M#29 = fb n a j n#3E0g #1A#19 #1B#18 #12#11 #13#10 #1A#19 #1B#18 #1A#19 #1B#18 #1A#19 #1B#18T T T #1A #1A J J #03 #03 #03#0F - - - Z Z Z Z Z Z ~ #14 #14 #14 Z Z#0A #0A C C CO ! ! ! #13 #13 #13 #13#2F #01 #01 #01 , , #18 #18 #18#189 q0 q1 b b a trap a a,b a b q2 You don't need to show trap states! Any arc not shown will by default go to a trap state. Example: Create a DFA that accepts even binary numbers that haveaneven number of 1's. De#0Cnition A language is regular i#0B there exists DFA M s.t. L=L#28M#29. 3 Chapter 2.2 Nondeterministic Finite Automata #28or Accepter#29 De#0Cnition An NFA=#28K,#06,#01,q 0 ,F#29 where K is #0Cnite set of states #06 is tape #28input#29 alphabet q 0 is initial state F #12 K is set of #0Cnal states. #01: subset of K#02#28#06#5Bf#0Fg#29#02K Example q0 q1 q2 q3 a a b b a Note: In this example with state q 0 and input a, Notation: #01#28q;a#29 = set of states reachable from q on a #01#28q 0 ;a#29= Example L=f#28ab#29 n j n#3E0g#5Bfa n bjn#3E0g De#0Cnition #28q i ;w#29`#03#28q j ;#0F#29 if and only if there is a walk from q i to q j labeled w. Example From previous example: What is q j in #28q 0 ;ab#29`#03#28q j ;#0F#29? What is q j in #28q 1 ;aba#29 `#03#28q j ;#0F#29? De#0Cnition: For an NFA M, L#28M#29=fw 2 #06 #03 j9p2Fs:t:#28q 0 ;w#29`#03#28p;#0F#29g The language accepted by nfa M is all strings w such that there exists a walk labeled w from the start state to #0Cnal state. 4 NFA vs. DFA: Which is more powerful? Example: #1A#19 #1B#18 #1A#19 #1B#18 #12#11 #13#10 #1A#19 #1B#18 - #0C #0C #0C #0C , , , #18 #18 #18#18: , , , , , , ,#09 ? - q0 q2 q1 a a b b Theorem Given an NFA M N =#28K N ;#06;#01 N ;q 0 ;F N #29, then there exists a DFA M D =#28K D ;#06;#0E D ;q 0 ;F D #29 such that L#28M N #29=L#28M D #29. Proof: We need to de#0Cne M D based on M N . K D = F D = #0E D : De#0Cnition: E#28q#29 is the closure of the set fqg E#28q#29=fp2Kj#28q;#0F#29 `#03#28p;#0F#29g Algorithm to construct M D 1. start state is E#28q 0 #29 2. While can add an edge #28a#29 Choose a state A=fq i ;q j ;:::q k g with missing edge for a 2 #06 #28b#29 Compute B = #01#28q i ;a#29#5B#01 #28 q j ;a#29#5B:::#5B#01#28q k ;a#29 #28c#29 apply closure to B, B = E#28B#29 #28d#29 Add state B if it doesn't exist #28e#29 add edge from A to B with label a 3. Identify #0Cnal states Note this proof is di#0Berent than the proof in the book. In the book instead of starting with the start state, it takes the closure of the start state, including all states reachable on #0F 5 Example: q0 q1 q3 q5 q2 q4 q6 ab a a b ? ? ? 6 sectnfaH.dvi