# Duke CPS 140 - Lecture (8 pages)

Previewing pages 1, 2, 3 of 8 page document
View Full Document

## Lecture

Previewing pages 1, 2, 3 of actual document.

View Full Document
View Full Document

## Lecture

40 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

View Full Document

## Access the best Study Guides, Lecture Notes and Practice Exams Unlocking...