CMU CS 15251 - Deterministic Finite Automata (7 pages)

Previewing pages 1, 2 of 7 page document View the full content.
View Full Document

Deterministic Finite Automata



Previewing pages 1, 2 of actual document.

View the full content.
View Full Document
View Full Document

Deterministic Finite Automata

162 views


Pages:
7
School:
Carnegie Mellon University
Course:
Cs 15251 - Great Theoretical Ideas in Computer Science
Great Theoretical Ideas in Computer Science Documents

Unformatted text preview:

Deterministic Finite Automata 15 251 Great Theoretical Ideas in Computer Science Lecture 20 October 29 2009 11 0 1 0 1 1 A machine so simple that you can understand it in less than one minute 0111 111 1 0 0 1 The machine accepts a string if the process ends in a double circle Anatomy of a Deterministic Finite 1 0 Automaton states 1 q1 0 q0 0 1 accept states F Anatomy of a Deterministic Finite Automaton q1 0 0 1 0 1 1 q12 The machine accepts a string if the start state q0 ends in q3a double circle states process q0 q2 0 0 The alphabet of a finite automaton is the set where the symbols come from 1 0 1 q3 The language of a finite automaton is the set of strings that it accepts 1 0 0 q0 0 1 1 q0 q1 1 L M All strings of 0s and 1s L M w w has an even number of 1s The Language of Machine M Notation A finite automaton is a 5 tuple M Q q0 F An alphabet is a finite set e g 0 1 Q is the set of states A string over is a finite length sequence of elements of is the alphabet Q Q is the transition function q0 Q is the start state For x a string x is the length of x F Q is the set of accept states The unique string of length 0 will be denoted by and will be called the empty or null string L M the language of machine M set of all strings machine M accepts A language over is a set of strings over M Q q0 F where Q q0 q1 q2 q3 Build an automaton that accepts all and only those strings that contain 001 0 1 Q Q transition function 1 q0 Q is start state 0 1 0 F q1 q2 Q accept states q1 0 1 0 1 1 M q0 0 q3 q2 0 1 q0 q1 q2 q3 0 q0 q2 q3 q0 1 q1 q2 q2 q2 q 0 1 q0 0 q00 1 q001 2 Build an automaton that accepts all strings whose length is divisible by 2 but not 3 Build an automaton that accepts exactly the strings that contain 01011 as a substring How about an automaton that accepts exactly the strings that contain an even number of 01 pairs A language is regular if it is recognized by a deterministic finite automaton L w w contains 001 is regular L w w has an even number of 1s is regular



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Deterministic Finite Automata and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Deterministic Finite Automata and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?