One Minute To Learn Programming: Finite AutomataSlide 2Meet “ABA” The Automaton!The Simplest Interesting Machine: Finite State Machine OR Finite AutomatonFinite AutomatonHow Machine M operates.Slide 7The set (or language) accepted by M is:Back to “ABA” The AutomatonWhat is the language accepted by this machine?Slide 11Slide 12What machine accepts this language?Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22The “grep” ProblemAutomata SolutionReal-life uses of finite state machinesSlide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Remember “ABA”?Slide 35Slide 36Slide 37MORAL:AdvertisementGreat Theoretical Ideas In Computer ScienceJohn Lafferty CS 15-251 Fall 2006Lecture 22 November 9, 2006 Carnegie Mellon UniversitybbabaaababOne Minute To Learn Programming:Finite AutomataSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Today we’ll talk about a programming language so simple that you can learn it in less than a minute.Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Meet “ABA” The Automaton!bbabaaababInput String Resultaba Acceptaabb Rejectaabba AcceptAcceptSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789The Simplest Interesting Machine:Finite State Machine OR Finite AutomatonSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Finite set of statesA start stateA set of accepting statesA finite alphabeta b # x 1State transition instructions1 2{ , , , , }o kQ q q q q KFinite Automatonoq 1 2, , ,ri i iF q q q K:( , )i jQ Qq a q iqjqaSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789How Machine M operates.M “reads” one letter at a time from the input string (going from left to right)M starts in state q0.If M is in state qi reads the letter a thenIf (qi. a) is undefined then CRASH.Otherwise M moves to state (qi,a)Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789M accepts the string x if when M reads x it ends in an accepting state.M rejects the string x if when M reads x it ends in a non-accepting state.M crashes on x if M crashes while reading x.Let M=(Q,,F,) be a finite automaton.Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789The set (or language) accepted by M is:{ }*Mk* 0 1 2 3L x | M accepts x All length k strings over the alphabet ...= �������������Notice that this is Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Back to “ABA” The AutomatonbbabaaababInput String Resultaba Acceptaabb Rejectaabba AcceptAcceptSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What is the language accepted by this machine?L = {a,b}* = all finite strings of a’s and b’sa,bSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What is the language accepted by this machine?a,ba,bSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What is the language accepted by this machine?L = all even length strings of a’s and b’sa,ba,bSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What machine accepts this language?L = all strings in {a,b}* that contain at least one aaa,bbSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What machine accepts this language?L = strings with an odd number of b’s and any number of a’sbaabSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What is the language accepted by this machine?L = any string ending with a bbbaaSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What is the language accepted by this machine?bba,baaSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What is the language accepted by this machine?L = any string with at least two a’sbba,baaSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What machine accepts this language?L = any string with an a and a bSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What machine accepts this language?L = any string with an a and a bbba,baabaSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789What machine accepts this language?L = strings with an even number of ab pairsabbaababSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789L = all strings containing ababb as a consecutive substringSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789L = all strings containing ababb as a consecutive substringba,baabbbbaaaaababaababInvariant: I am state s exactly when s is the longest suffix of the input (so far) that forms a prefix of ababb.Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Problem:Does the string S appear inside the text T ?The “grep” ProblemInput:• text T of length t• string S of length nCost: O(nt) comparisons1 2 3, , , ,ta a a aK K K K K K symbols n6 4 447 4 4 48Naïve method:Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Automata 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.Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Real-life uses of finite state machines•grep•coke machines•thermostats (fridge)•elevators•train track switches•lexical analyzers for parsersSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Any L is defined to be a language.L is just a set of strings. It is called a language for historical reasons.Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Let L be a language.L is called a regular language if there is some finite automaton that accepts L.In this lecture we have seen many regular languages.• • even length strings• strings containing ababbSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Theorem: Any finite langage is regular.Proof: Make a machine with a “path” for each string in the language, sharing prefixes Example: L = {a, bcd, ac, bb}bdacbcSteven Rudich: www.cs.cmu.edu/~rudich rudich0123456789Are all languages regular?Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789 , , , ,n na b ab aabb aaabbb KConsider the languagei.e., a bunch of a’s followed by an equal number of b’sNo finite automaton accepts this language.Can you prove this?Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789anbn is not regular. No machine has enough states to keep track of the number of a’s it might encounter.Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789That is a fairly weak argument. Consider the following example…Steven Rudich:
View Full Document
Unlocking...