Great Theoretical Ideas In Computer Science Victor Adamchik Danny Sleator Lecture 20 CS 15 251 Mar 30 2010 Finite Automata Spring 2010 Carnegie Mellon University Deterministic Finite Automata A machine so simple that you can understand it in less than one minute Wishful thinking 11 0 1 0 1 1 0111 111 1 0 0 1 The machine accepts a string if the process ends in a double circle start state q0 0 11 accept states F 1 0 1 1 0111 111 1 0 transitions 0 1 states The machine accepts a string if the process ends in a double circle Anatomy of a Deterministic Finite Automaton The singular of automata is automaton The alphabet of a finite automaton is the set where the symbols come from for example 0 1 The language of a finite automaton is the set of strings that it accepts The Language L M of Machine M 0 1 q0 L M All strings of 0s and 1s The language of a finite automaton is the set of strings that it accepts The Language L M of Machine M 0 0 0 1 q0 q1 1 1 L M w w has an even number of 1s Notatio n set e g 0 1 An alphabet is a finite A string over is a finite length sequence of elements of For x a string x isthe length of x The unique string of length 0 will be denoted by and will be called the empty or null string A language over is a set of strings over A finite automaton is M Q q0 F Q is the finite set of states is the alphabet Q Q is the transition function q0 Q is the start state F Q is the set of accept states L M the language of machine M set of all strings machine M accepts M Q q0 F where Q q0 q1 q2 q3 0 1 q0 Q is start state F q1 q2 Q accept states Q Q transition function q1 0 1 q0 0 M q3 1 0 1 q2 0 1 q0 0 1 q0 q1 q1 q2 q2 q2 q3 q2 q3 q0 q2 The finite state automata are deterministic if for each pair Q of state and input value there is a unique next state given by the transition function There is another type machine in which there may be several possible next states Such machines called nondeterministic EXAMPLE Build an automaton that accepts all and only those strings that contain 001 0 1 0 1 0 0 1 0 00 1 001 Build an automaton that accepts all binary numbers that are divisible by 3 i e L 0 11 110 1001 1100 1111 10010 10101 1 0 1 0 1 0 language over is a set of strings over 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 regu Determine the language recognized by 0 1 1 0 L M 1n n 0 1 2 Determine the language recognized by 0 1 0 0 1 0 1 1 L M 1 01 Determine the language recognized by 0 0 1 1 0 1 0 1 L M 0n 0n10x n 0 1 2 and x is any string DFA Membership problem Determine whether some word belongs to the language Theorem The DFA Membership Problem is solvable in linear time Let M Q q0 F and w w1 wm Algorithm for DFA M p q0 for i 1 to m do p p wi if p F then return Yes else return Equivalence of two DFAs Definition Two DFAs M1 and M2 over the same alphabet are equivalent if they accept the same language L M1 L M2 Given a few equivalent machines we are naturally interested in the smallest one with the least number of states Union Theorem Given two languages L1 and L2 define the union of L1 and L2 as L1 L2 w w L1 or w L2 Theorem The union of two regular languages is also a regular language Theorem The union of two regular languages is also a regular language Proof Sketch Let 1 M1 Q1 1 q0 F1 be finite automaton for L1 2 and M2 Q2 2 q0 F2 be finite automaton for L2 We want to construct a finite automaton M Q q0 F that recognizes L L1 L2 Idea Run both M1 and M2 at the same time pairs of states one from M1 and one from Q q1 q2 q1 Q1 and q2 Q2 Q1 Q 2 Theorem The union of two regular languages is also a regular language 0 0 0 1 q0 q1 1 0 1 1 0 p0 p1 0 Automaton for Union 0 1 p0 q0 p0 q1 1 0 0 0 0 0 1 p1 q0 p1 q1 1 The Regular Operations Union A B w w A or w B Intersection A B w w A and w B Negation A w w A Reverse AR w1 wk wk w1 A Concatenation A B vw v A and w B Star A w1 wk k 0 and each wi A Reverse Reverse AR w1 wk wk w1 A How to construct a DFA for the reversal of a language The direction in which we read a string should be irrelevant If we flip transitions around we might not get a DFA The Kleene closure A Star A w1 wk k 0 and each wi A From the definition of the concatenation we definite An n 0 1 2 recursively A0 An 1 An A A is a set consisting of concatenations of arbitrary many strings from A A UAk k 0 The Kleene closure A What is A of A 0 1 All binary strings What is A of A 11 All binary strings of an even number of 1s Regular Languages Are Closed Under The Regular Operations We have seen part of the proof for Union The proof for intersection is very similar The proof for negation is easy Theorem Any finite language is regular Claim 1 Let w be a string over an alphabet Then w is a regular language Proof By induction on the number of characters If a and b are regular then ab is regular Claim 2 A language consisting of n strings is regular Proof By induction on the number of strings If a then L a is regular Pattern Matching Input Text T of length t string S of length n Problem Does string S appear inside text T Na ve method a1 a2 a3 a4 a5 at Cost Roughly nt comparisons Automata Solution Build a machine M that accepts any string with S as a consecutive substring Feed the text to M Cost t comparisons time to build M As luck would have it the Knuth Morris Pratt algorithm builds M quickly Real life Uses of DFAs Grep Coke Machines Thermostats fridge Elevators Train Track Switches Lexical Analyzers for Parsers Are all languages regular Consider the language L …
View Full Document
Unlocking...