Chapter 4 Finite Automata Models of Computation 2 Different Kinds of Automata • Automata are distinguished by the temporary memory • Finite Automata : no temporary memory • Pushdown Automata • Turing Machines Sept2011 : stack : random access memory Theory of Computer Science 3 Finite Automaton temporary memory Finite Automaton input memory output memory Example: Vending Machines (small computing power) 4 Pushdown Automaton Stack Push, Pop Pushdown input memory Automaton output memory Example: Compilers for Programming Languages (medium computing power) 5 Turing Machine Random Access Memory Turing input memory Machine output memory Examples: Any Algorithm (highest computing power) 6 Power of Automata Finite Pushdown Turing Automata Automata Machine Less power More power Solve more computational problems Sept2011 Theory of Computer Science 7 Finite Automata http://www.youtube.com/watch?v=d7ZAcym3DUw 8 Finite Automata (FA) • Finite - Every FA has a finite number of states • Automata (singular automaton) means “machine” • A simple class of machines with limited capabilities. • Good models for computers with an extremely limited amount of memory. • E.g., an automatic door : a computer with only a single bit of memory. 9 Examples • Elevator controller – state : n-th floor – input : input received from the buttons. • • • • Dishwashers Washing Machines Digital watches Calculators 10 State Diagram LIFT: • move to level 1 when person push button 1 • move to level 2 when person push button 2 • move to level 3 when person push button 3 Level 3 Level 2 Level 1 11 State Transition Table States: Input: Level1, Level2, Level3 1 someone push button 1 2 someone push button 2 3 someone push button 3 INPUT STATE Level1 Level2 Level3 1 2 3 Level1 Level1 Level1 Level2 Level2 Level2 Level3 Level3 Level3 12 Finite Automaton Input String Output Finite Automaton “Accept” or “Reject” 13 Definition of FA • A finite automaton (FA) is a collection of 3 things: – A finite set of states, one of them will be the initial or start state, and some (maybe none) are final states. – An alphabet of possible input letters. – A finite set of transition rules that tell for each state and for each input (alphabet) which state to go to next. 14 State Diagram transition Initial / start state final / accepting state – start state = q1 state – final state = q2 – transitions = each arrows – alphabet = each labels • When this automaton receives an input string such as 1101, it processes that string and produce output (Accept or Reject). 15 Initial Configuration a b b a Input String a,b q5 b q0 a a a b q1 b q2 b q3 a a, b q4 16 Reading the Input a b b a a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 17 a b b a a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 18 a b b a a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 19 a b b a a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 20 Input finished a b b a a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 accept 21 Rejection a b a a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 22 a b a a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 23 a b a a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 24 a b a a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 25 Input finished a b a a,b q5 b q0 a a a b q1 b q2 b q3 a reject a,b q4 26 Another Rejection a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 27 a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 reject 28 Language of Machine • If A is the set of all strings accepted by machine M, we say that A is the language of machine M. L(M) = A • L(M) = {strings that bring M to an accepting state} • M recognizes A (only 1 language) • M accepts strings (several strings) • If M accepts no strings, it still recognizes one language, empty language 29 Formal Definition • A finite automaton is a 5-tuple (Q, , , q0, F) where – – – – – Q is a finite set of states, is a finite set of alphabets, : Q x Q is the transition function, q0 Q is the start state, and F Q is the set of accept states (final states) Note: - delta 30 Example : Finite Automaton M1 • M1= (Q,,,q1,F) , where – Q = {q0, q1}, – = {a, b}, – is described as – q0 is the start state, and – F = {q0, q1}. a b q0 q0 q1 q1 q0 q1 31 Example : Finite Automaton M1 What is the language of M1? L(M1) = (a + b)*1+00+01)* 32 Example : Finite Automaton M2 0 1 1 q2 q1 0 • M2 = (Q, , , q0, F) , where –Q= –= – is described as – q1 is the start state, and – F = { }. 0 1 q1 q2 33 Example : Finite Automaton M2 0 1 1 q2 q1 0 What is the language of M2? L(M2) = {w | w ends in a 1} 34 Empty String 0 1 q1 1 q2 0 • If the start state is also a final state, what string does it automatically accept ? • L(M3) = { w | w is the empty string or ends in a 0} 35 Example : Finite Automaton M4 • M4= (Q, , , S, F) , where S b a a r1 q1 b a q2 b b a b r2 a – Q= r1 – = – is described as S a b q1 r1 q1 q1 q2 q2 q1 q2 r1 r2 r1 r2 r2 r1 – S is the start state, and – F = { q1, r1 }. L(M4) = strings that start and end with the same symbol. # a(a + bb*a)* + b(b + aa*b)* 36 FA Design : Example • Question: Design an FA to accept the language of all strings over {0, 1} that contain the string 001 as a substring, e.g.: accept 0010, 1001, 001, 111001111, but not 11, 000. • Thinking of… for every input, skip over all 1s. If we read 0, note that we may have just seen the first of the 3 symbols 001. Then if we see a 1, go back to skipping over 1s. Then … proceed … to seek for another two 0s ... Theory of Computer Science 37 Example : Strings with substring 001 • So we can conclude there are four possibilities: – Haven’t just seen any symbols of 001 – Have just seen a 0 – Have just seen 00 – Have seen 001 • Assign the states q, q0, q00, q001 to these possibilities. We can design the transition by observing that from q reading a 1, we stay in q, but reading a 0 we move to q0. In q0, reading a 1 we return to q, but reading a 0 we move to q00. In q00, reading a 1 we move to q001, but reading a 0 leaves us in q00. finally, in q001 reading a 0 or a 1 leaves us in q001. Theory of Computer Science 38 Example : Strings with substring 001 • The start state is q, and the only accept state is q001. or Theory of Computer Science 39 Designing a FA – An example • Draw an FA accepting the language of all string over {a, b} containing exactly two a’s. • b*ab*ab* • IN aa, aba, baba, aabb, bbbaa. • NOT a, ab, ba, bb Sept2011 Theory of Computer Science 40 How to convert RE to FA • General rules: • a+b • ab • a* Sept2011 Theory of Computer Science 41 How to convert RE to FA • ab*a – aa, aba, abba, abbba. • (a + b)c – aa, bc • a(bc)* – a, abc, abc Sept2011 Theory of Computer Science 42 Computation of FA, ⊢M • Way to describe the computation of a DFA • What state the DFA is currently in, and what string is left to process – (q0, 0010) Machine is in state q0, has 0010 left to process – (q1, 010) Machine is in state q1, has 010 left to process – (q3, ) Machine is in state q3 at the end of the computation (accept iff q3 ∈ F) • Binary relation ⊢M : What machine M yields in one step – (q0, 0010) ⊢M (q1, 010) Theory of Computer Science 43 Accepted @ Rejected Strings • To trace all computations that process the string 0010. • [q0 , 0010] ⊢ [q1 , 010] ⊢ [q2 , 10] ⊢ [q3 , 0] ⊢ [q3 , λ] • Stop at q3 (final state) and all alphabet is traced (string is empty); • Hence, string 0010 is accepted by machine. Theory of Computer Science 44 Determinism • So far, every step of a computation follows in a unique way from the preceding step. • When the machine is in a given state and reads the next input symbol, we know what the next state will be – it is called deterministic computation • Deterministic Finite Automata (DFA) 45 Why DFA? • Why are these machines called “Deterministic Finite Automata” • Deterministic - Each transition is completely determined by the current state and next input symbol. That is, for each state / symbol pair, there is exactly one state that is transitioned to. Sept2011 Theory of Computer Science 46 Nondeterminism • In a nondeterministic machine, several choices may exist for the next state at any point. • Nondeterministic Finite Automata (NFA) • Nondeterminism is a generalization of the determinism, so every DFA is automatically a NFA. 47 Example of DFA vs. NFA DFA NFA 48 Differences between DFA & NFA • Every state of DFA always has exactly one exiting transition arrow for each symbol in the alphabet while the NFA may has zero, one or more. • In a DFA, labels on the transition arrows are from the alphabet while NFA can have an arrow with the label . 49 One exiting transition arrow q0 , 1 q1 0 q0 1 q1 0, 1 q 2 50 More (two) exiting transition arrows ( q1,0) {q0 , q2 } 0 q0 1 q1 0, 1 q 2 51 More (two) exiting transition arrows ( q0 , ) {q0 , q2} 0 q0 1 q1 0, 1 q 2 52 Zero exiting transition arrow – undefined transiton ( q2 ,1) 0 q0 1 q1 0, 1 q 2 53 NFA vs. DFA Features DFA NFA Choice of transition Single Multiple Input label Alphabets only Alphabets or or Undefined transitions No Possible • Converting NFA to DFA • Remove all undefined states into trap state(s) • Remove empty string inputs ( or ) • Remove multiple states transitions 54 How does the NFA work? • When we are at a state with multiple choices to proceed (including symbol), the machine splits into multiple copies of itself and follow all the possibilities in parallel. • Each copy of the machine takes one of possible ways to proceed and continuous as before. If there are subsequent choices, the machine splits again. • If the next input symbol doesn’t appear on any of the arrows exiting the state occupied by a copy of the machine, that copy dies. • If any one of these copies is in an accept state at the end of the input, the NFA accepts the input string. 55 Tree of possibilities • Think of a nondeterministic computation as a tree of possibilities • The root of the tree corresponds to the start of the computation. • Every branch point in the tree corresponds to a point in the computation at which the machine has multiple choices. • The machine accepts if at least one of the computation branches ends in the an accept state. 56 Tree of possibilities Deterministic computation start Nondeterministic computation reject accept or reject accept 57 Example: 010110 Start Read symbol q1 0 q1 1 q2 q1 q3 0 q3 q1 1 q1 q2 q3 q4 1 q1 q2 q3 q4 q4 0 q1 q3 q4 q4 58 Properties of NFA • Every NFA can be converted into an equivalent DFA. • Constructing NFAs is sometimes easier than directly construction DFAs. • NFA may be much smaller than it DFA counterpart. • NFA’s functioning may be easier to understand. • Good introduction to non-determinism in more powerful computational models because FA are especially easy to understand. 59 Example: Converting NFA into DFA NFA: recognizes language which contains 1 in the third position from the end Equivalent DFA: 60 Formal definition of NFA • A NFA is a 5-tuple (Q, , , q0, F) , where – Q is a finite set of states, – is a finite alphabet, – : Q x P(Q) is the transition function, – q0 is the start state, and – F Q is the set of accept states. Notation: P(Q) is called power set of Q (a collection of all subsets of Q). and = {} 61 Example: Formal definition of NFA NFA M1: • Formal definition of N1 is (Q, , , q0, F) , where – Q = {q1,q2,q3,q4} – = {0,1} – is given as – q0 is the start state, and – F = {q4} q1 q2 q3 q4 0 {q1} {q3} {q4} 1 {q1,q2} {q4} {q4} {q3} 62 Example of NFA • L = {w ∈ {a, b} : w starts with a} • What is the RE for the language? a(a+b)* • What happen if the 1st input is b? Theory of Computer Science 63 Example of NFA • L = {w ∈ {a, b} : w contains the substring aa} • What is the RE for the language? (a+b)*aa(a+b)* • What happen if the 1st input is a? • Does the machine accept abaa? (q0, abaa) (q0, baa) (q1, baa) reject Sept2011 (q0,aa) (q0, a) (q1, a) Theory of Computer Science (q0, e) reject (q1, e) reject (q2, e) accept 64 Regular Languages Definition: • A language L is regular if there is FA M such that L = L(M) Observation: • All languages accepted by FAs form the family of regular languages 65 Regular Languages • Examples of regular languages: {abba} {, ab, abba} {awa : w {a, b}*} {anb : n 0} {all strings with prefix ab} {all strings without substring 001} There exist automata that accept these languages. 66 Non-Regular Languages • There exist languages which are not regular : • Example : n n L = {a b : n 0} There is no FA that accepts such a language. 67 Example of DFA • L(M) = {anb : n 0} a, b a q0 b q1 accept a,b q2 trap state 68 Example of DFA • L(M) = {, ab, abba} M a,b q5 b q0 a accept a a b q1 b q2 b q3 a accept a,b q4 accept 69 Example of DFA • • • • Input Alphabet = {a, b} Set of States Q = {q0, q1, q2, q3, q4, q5} Initial State = q0 Set of Accepting States F = {q4} a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 70 Transition Functions () • :QxQ a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 71 q0 , a q1 a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 72 q0 , b q5 a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 73 q2 , b q3 a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 74 q0 q1 q2 q3 q4 q5 a q1 q5 q5 q4 q5 q5 b q5 q2 q3 q5 q5 q5 Transition Function () a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 75 Extended Transition Function (*) • * : Q x * Q a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 76 • * (q0, ab) = q2 a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 77 • * (q0, abba) = q4 a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 78 • * (q0, abbbaa) = q5 a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 79 Observation: if there is a walk from q to q’ with label w then * (q, w) = q’ w q q W = 1 2 …k q 1 2 k q 80 Example: There is a walk from q0 to q5 with label abbbaa * (q0, abbbaa) = q5 a,b q5 b q0 a a a b q1 b q2 b q3 a a,b q4 81 Language Accepted by FAs • For a FA M = (Q, , , q0, F) • Language accepted by M : L(M) = (w *: *(q0, w) F) q0 w q q F 82 Observation • Language rejected by M : L(M) = (w *: *(q0, w) F) q0 w q q F 83 Example (NFA or DFA ?) • Create a FA for L(M) = {awa : w {a, b}*} a, b q0 a q2 a q3 • What happen if the 1st input is b? • What happen if the input are bab, abab, … ? 84 Example of DFA • L(M) = {awa : w {a, b}*} b a b q0 a q2 q3 a b q4 a,b 85 Example • L(M) = {all strings without substring 001} 0 1 0,1 1 0 0 00 1 001 0 86 Example • L(M) = {all strings with prefix ab} a,b q0 a b q1 b accept a q3 q2 a,b 87 Regular Grammars , Finite Automata and Regular Expression A context-free grammar is called regular if each rule is the form. A → aB , A → a , or A → λ Let grammar G be: G : S → aS | aA | λ A → bA | b a M: S a A Regular Grammars , Finite Automata and Regular Expression A context-free grammar is called regular if each rule is the form. A → aB , A → a , or A → λ Let grammar G be: G : S → aS | aA | λ A → bA | b a M: S b a A b Z Derivation Computation S→ aS [ S, aabb]┣ {S, abb] String processed a →aaA ┣ [A, bb] aa →aabA ┣ [A, b] aab →aabb ┣ [A, λ] aabb Derivation Computation S→ aS [ S, aabb]┣ {S, abb] String processed a →aaA ┣ [A, bb] aa →aabA ┣ [A, b] aab →aabb ┣ [ Z, λ] aabb Regular Grammars , Finite Automata and Regular Expression Let grammar G be: S → a* aA + λ G : S → aS | aA | λ A → bA | b A→ b* b S → a* ab*b + λ Thus, regular expression for grammar G or NFA M is: a+b+ + λ a*ab*b + λ OR a M: S b a A b Z Example Let grammar G be: G : S → aS | bB | a B → bB | λ M: a b B S a Z Example Let grammar G be: G : S → aS | bB | a B → bB | λ M: b a b B S a Z Example Let grammar G be: G : S → aS | bB | a B → bB | λ S → a*bB + a*a B → b* S → a*bb* + a*a M: b a b B S a Z The regular expression is: a*bb* + a*a OR a*(bb* + a) Example A regular grammar with alphabet { a, b } that generates strings with an even number of a’s and an odd number of b’s. b B a b a S a b C a b A S → aB | bA | λ A → aC | bS B → aS | bC C → aA | bB Example: NFA to DFA The NFA. M accepted the language a+ b+ M: a qo b q1 a b a b q0 {q0, q1} Ø q1 Ø {q1, q2} q2 Ø Ø q2 Example: NFA to DFA The NFA. M accepted the language a+ b+ a b qo {q0, q1} Ø q1 Ø {q1, q2} q2 Ø Ø DM : a a b {qo} {qo ,q1} b {q1,q2} a ø a,b b Exercise • For the alphabet {0, 1} give regular expression and finite automata for each language: – All strings containing exactly two 0’s. – All strings containing at least two 0’s. – All strings containing 00 as substring. • For the alphabet {a, b} give NFA for each language: – 1. All strings starting with abb. – 2. All strings ending with abb. – 3. All strings containing abb as a substring. Sept2011 Theory of Computer Science 98

1/--pages