Great Theoretical Ideas In Computer Science Victor Adamchik Danny Sleator Lecture 20 CS 15 251 Mar 30 2010 Spring 2010 Deterministic Finite Automata Carnegie Mellon University A machine so simple that you can understand it in less than one minute Finite Automata Wishful thinking 11 0 0 1 1 start state q0 0 1 0111 accept states F 1 0 1 1 111 0 11 1 0 0111 111 0 1 The machine accepts a string if the process ends in a double circle Anatomy of a Deterministic Finite Automaton transitions 1 The machine accepts a string if the process ends in a double circle The language of a finite automaton is the set of strings that it accepts states The Language L M of Machine M The singular of automata is automaton The alphabet of a finite automaton is the set where the symbols come from for example 0 1 1 0 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 1 Notation The Language L M of Machine M 0 0 q0 0 1 q1 1 1 L M w w has an even number of 1s An alphabet is a finite set e g 0 1 A string over is a finite length sequence of elements of For x a string x is the 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 M Q q0 F where Q q0 q1 q2 q3 0 1 Q is the finite set of states q0 Q is start state is the alphabet F q1 q2 Q accept states Q Q is the transition function Q Q transition function q0 Q is the start state F Q is the set of accept states q1 0 q0 q1 q2 q3 1 0 1 1 L M the language of machine M set of all strings machine M accepts M q0 q2 0 0 q3 1 0 q0 q2 q3 q0 1 q1 q2 q2 q2 EXAMPLE 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 Build an automaton that accepts all and only those strings that contain 001 0 1 0 1 0 0 0 00 1 001 1 2 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 Determine the language recognized by A 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 regular Determine the language recognized by 0 0 1 1 1 0 0 1 0 1 0 1 L M 1n n 0 1 2 Determine the language recognized by 1 DFA Membership problem Determine whether some word belongs to the language Theorem The DFA Membership Problem is solvable in linear time 0 0 L M 1 01 1 0 1 0 1 L M 0n 0n10x n 0 1 2 and x is any string 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 No 3 Equivalence of two DFAs Union Theorem 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 Theorem The union of two regular languages is also a regular language 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 Idea Run both M1 and M2 at the same time Proof Sketch Let 1 M1 Q1 1 q0 F1 be finite automaton for L1 and 2 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 Theorem The union of two regular languages is also a regular language 0 0 q0 Q pairs of states one from M1 and one from M2 q1 q2 q1 Q1 and q2 Q2 Q1 Q2 Automaton for Union 0 0 1 p0 q0 q1 p0 q1 1 1 0 1 p0 1 1 0 p1 0 0 0 0 p1 q0 0 0 1 p1 q1 1 4 The Regular Operations Union A B w w A or w B Reverse Reverse AR w1 wk wk w1 A 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 How to construct a DFA for the reversal of a language Star A w1 wk k 0 and each wi A 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 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 n 1 A An A A is a set consisting of concatenations of arbitrary many strings from 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 A UAk k 0 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 5 Pattern Matching Input Text T of length t string S of length n Problem Does string S appear inside text T Automata Solution Build a machine M that accepts any string with S as a consecutive substring Feed the text to M Na ve method a1 a2 a3 a4 a5 at Cost Roughly nt comparisons Real life Uses of DFAs Grep Cost t comparisons time to build M As luck would have it the Knuth Morris Pratt algorithm builds M quickly Are all languages regular Coke Machines Thermostats fridge Elevators Train Track Switches …
View Full Document
Unlocking...