## Lecture

Previewing pages
*1, 2, 3*
of
actual document.

**View the full content.**View Full Document

## Lecture

0 0 54 views

- Pages:
- 8
- School:
- Duke University
- Course:
- Cps 140 - Mathematical Foundations of Computer Science

**Unformatted text preview:**

CPS 140 Mathematical Foundations of CS Dr Susan Rodger Section Finite Automata Ch 2 handout Deterministic Finite Accepter or Automata A DFA Q q0 F input tape a a b b tape head a b head moves current state 0 1 where Q is finite set of states is tape input alphabet q0 is initial state F Q is set of final states Q Q Example Create a DFA that accepts even binary numbers Transition Diagram 1 0 0 q0 q1 1 M Q q0 F Tabular Format q0 q1 0 q1 q1 1 q0 q0 Example of a move q0 1 1 Algorithm for DFA Start in start state with input on tape q current state s current symbol on tape while s blank do q q s s next symbol to the right on tape if q F then accept Example of a trace 11010 Pictorial Example of a trace for 100 1 3 1 1 0 2 0 1 0 q0 q0 q1 q1 0 0 4 1 0 0 0 q0 q0 q1 q1 Definition q q q wa q w a Definition The language accepted by a DFA M Q q0 F is set of all strings on accepted by M Formally L M w q0 w F 2 Trap State Example L M bn a n 0 b q0 b a q2 q1 a a trap b a b 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 have an even number of 1 s Definition A language is regular iff there exists DFA M s t L L M 3 Chapter 2 2 Nondeterministic Finite Automata or Accepter Definition An NFA Q q0 F where Q is finite set of states is tape input alphabet q0 is initial state F Q is set of final states Q 2Q Example b q1 a b q0 q3 a a q2 Note In this example q0 a Example L ab n n 0 an b n 0 Definition qj qi w if and only if there is a walk from qi to qj labeled w Example From previous example q0 ab q0 aba Definition For an NFA M L M w q0 w F 6 The language accepted by nfa M is all strings w such that there exists a walk labeled w from the start state to final state 4 2 3 NFA vs DFA Which is more powerful Example q1 b a a q0 b q2 Theorem Given an NFA MN QN N q0 FN then there exists a DFA MD QD D q0 FD such that L MN L MD Proof We need to define MD based on MN QD FD D Algorithm to construct MD 1 start state is q0 2 While can add an edge a Choose a state A qi qj qk with missing edge for a b Compute B qi a qj a qk a c Add state B if it doesn t exist d add edge from A to B with label a 3 Identify final states 4 if L MN then make the start state final 5 Example a q1 b q3 q5 a q0 a q2 b q4 Minimizing Number of states in DFA Why Algorithm Identify states that are indistinguishable These states form a new state Definition Two states p and q are indistinquishable if for all w q w F p w F p w 6 F q w 6 F Definition Two states p and q are distinquishable if w s t q w F p w 6 F OR q w 6 F p w F 6 q6 Example b a b a A B C a b a b a D b b E F b a 7 a G Example a b H a I b a a A b b B C a b a b b a D b E F b a 8 a G

View Full Document