To login with Google, please enable popups

or

Don’t have an account? Sign up

To signup with Google, please enable popups

or

Sign up with Google or Facebook

or

By signing up I agree to StudyBlue's

Terms of Use and Privacy Policy

Already have an account? Log in

Sectnfah.pdf

- StudyBlue
- Iowa
- Iowa State University
- Computer Engineering
- Computer Engineering 140
- Dr. Susan Rodgers
- Sectnfah.pdf

Steve M.

File Size:
6
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