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 Theorem The union of two regular languages is also a regular language Proof Sketch Let M1 Q1 1 q10 F1 be finite automaton for L1 and 2 M2 Q2 2 q0 F2 be finite automaton for L2 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 Idea Run both M1 and M2 at the same time Q pairs of states one from M1 and one from M2 q1 q2 q1 Q1 and q2 Q2 Q1 Q2 We want to construct a finite automaton M Q q0 F that recognizes L L1 L2 3 Theorem The union of two regular languages is also a regular language 0 Automaton for Union 1 0 q0 p0 q1 p0 1 1 q0 q1 1 1 1 0 0 0 0 1 q0 p1 0 p0 q1 p1 1 p1 0 Automaton for Intersection 1 q0 p0 q1 p0 1 0 0 0 0 Theorem The union of two regular languages is also a regular language Corollary Any finite language is regular 1 q0 p1 q1 p1 1 The Regular Operations Union A B w w A or w B Intersection A B w w A and w B Reverse AR w1 wk wk w1 A Regular Languages Are Closed Under The Regular Operations Negation A w w A Concatenation A B vw v A and w B We have seen part of the proof for Union The proof for intersection is very similar The proof for negation is easy Star A w1 wk k 0 and each wi A 4 The Grep Problem Automata Solution Input Text T of length t string S of length n Build a machine M that accepts any string with S as a consecutive substring Problem Does string S appear inside text T Feed the text to M Na ve method a1 a2 a3 a4 a5 at Cost t comparisons time to build M As luck would have it the Knuth Morris Pratt algorithm builds M quickly Cost Roughly nt comparisons Real life Uses of DFAs Grep Are all languages regular Coke Machines Thermostats fridge Elevators Train Track Switches Lexical Analyzers for Parsers Consider the language L anbn n 0 i e a bunch of a s followed by an equal number of b s No finite automaton accepts this language Can you prove this anbn is not regular No machine has enough states to keep track of the number of a s it might encounter 5 L strings where the of occurrences of the pattern ab is equal to the number of occurrences of the pattern ba That is a fairly weak argument Can t be regular No machine has enough states to keep track of the number of occurrences of ab Consider the following example a b a a b a b b a b L strings where the of occurrences of the pattern ab is equal to the number of occurrences of the pattern ba Can t be regular No machine has enough states to keep track of the number of occurrences of ab M accepts only the strings with an equal number of ab s and ba s Pigeonhole principle Let me show you a professional strength proof that anbn is not regular This is the kind of proof we expect from you Given n boxes and m n objects at least one box must contain more than one object Letterbox principle If the average number of letters per box is x then some box will have at least x letters similarly some box has at most x 6 Theorem L anbn n 0 is not regular Proof by contradiction Assume that L is regular Then there exists a machine M with k states that accepts L For each 0 i k let Si be the state M is in after reading ai i j k such that Si Sj but i j How to prove a language is not most of the time regular Assume it is regular hence is accepted by a DFA M with n states Show that there are two strings s and s which both reach some state in M usually by pigeonhole principle Then show there is some string t such that string st is in the language but s t is not However M accepts either both or neither M will do the same thing on …
View Full Document
Unlocking...