Finite Automata (DFA) Lesson

AUTOMATA THEORY AND FORMAL LANGUAGES  MODULE 2 Finite Automata  SUBMODULE 1 Deterministic Finite Automata (DFA) At the end of the module, the learner should be able to: Demonstrate understanding of the theory of Finite Automata Apply the concepts of Deterministic Finite...

AUTOMATA THEORY AND FORMAL LANGUAGES  MODULE 2 Finite Automata  SUBMODULE 1 Deterministic Finite Automata (DFA) At the end of the module, the learner should be able to: Demonstrate understanding of the theory of Finite Automata Apply the concepts of Deterministic Finite Automata (DFA) Determine acceptability of a string using Extended Transition of DFA Automata Theory Is the study of abstract computing device, or “machines”. It deals with the logic of computation with respect to simple machines, referred to as automata. It deals with the definitions and properties of mathematical models of computation such as Finite Automaton and Context-Free Grammar. Through automata, computer scientists are able to understand how machines compute functions and solve problems. Brief History of Automata Conceived the first infinite model of computation in 1936 * Alan Turing First to present a description of finite automata in 1943: * Warren McCulloch * Walter Pitts Generalized automata theory to a much more powerful machine in 1955: * G. H. Mealy * E.F. Moore Applications of Automata and Formal Languages 1. It serves as a preparation and introduction to circuit design. 2. Knowledge of automata is very important in designing compilers. 3. Regular expressions in automata provide a thousand and one uses for professional programmers. 4. Searching for patterns in texts can be carried out efficiently using automata. 5. Automata and its formal languages are useful in natural language processing. 6. Algebraic theory of recognizable language can be developed using automata theory and its languages. Terminologies Alphabet o A finite, nonempty set of symbols. Denoted by , whose elements are called symbols. o  + denotes set of all nonempty strings on  o * =  +  { λ } Examples:  = { 0, 1 } → the binary alphabet  = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } → 10 element set of decimal digits  = { a, b, c,... , x, y, z } → 26 element set of lowercase characters of the English language Terminologies String o A list of symbols from an alphabet. o An ordered n-tuple of elements of ∑ , written without punctuation. Examples: 1101 → from  = { 0, 1 } of length 4 a, ab, aac, bbac → from  = {a, b, c} of length 1, 2, 3 and 4 respectively * → set of all strings over  of any finite length. → there is a unique string of length zero over  called the null string (empty string) and is denoted by ε. Terminologies Concatenation of two strings u, v ∈ ∑* o Is the string uv obtained by joining the strings end-to-end. Example: if u = ab, v=ra and w=cad then vu=raab uu=abab and wv=cadra This generalizes to the concatenation of three or more strings. i.e. : uvwuv = abracadabra Terminologies Length of a String o The number of positions for symbols in the string. Denoted by | w |. Let w = a1a2... ak  *, where a1a2... ak  . Then k is called the length of the string: w = a1a2... ak, and this is expressed by writing | w |. Examples: | 011 | = 3 | λ | = 0 Terminologies Empty String o The string of zero length is called the empty string. This is denoted by  or . o The empty string plays the role of 0 in a number system. Reverse String o If w = w1 w2…wn where w1  ∑ the reverse of w is wn wn-1…w1. Substring o z is a substring of w if z appears consecutively within w. Example: deck is a substring of abcdeckabcjkl. Terminologies Suffix if w= xv for some x, then v is suffix of w Prefix if w= vy for some y, then v is suffix of w Lexicographic ordering of string is the same as the dictionary ordering, except the shorter strings precede longer strings. Example: Lexicographic ordering of all strings over the alphabet {0,1} is (, 0, 1, 00, 01, 11, 000, …). Terminologies Language o A set of strings from the same alphabet. Denoted by L(M). o The set of all strings, including the empty string over and alphabet ∑ is denoted as ∑*. o Infinite language L are denoted as: L={w  ∑+: w has property P} Example: L(M) = {, 01, 10, 0011, 0101, 1001,... } L1 = {w  {0,1}*: w has an equal number of 0’s and 1’s. L2 = {w  ∑+: w = wR} where wR is the reverse string of w. Terminologies Concatenation of Language If L1 and L2 are languages over ∑, their concatenation is L = L1 L2 or simply L= L1L2 , where: L={w ∈ ∑+ : w = x y for some x ∈ L1 and y ∈ L2} Example: Given ∑={0,1} L1 = {w ∈ ∑+ : w has an even number of 0’s} L2 = {w: w starts with a 0 and the rest of the symbols are 1’s} Terminologies Powers of an Alphabet o The set of all strings of a certain length from . o Denoted by k Examples: 0 = {  } 1 = { 0, 1 } 2 = { 00, 01, 10, 11 } Note: The set of all strings over an alphabet  is conventionally denoted by:  * = 0  1  2 ... Examples: { 0, 1 }* = { , 0, 1, 00, 01, 10, 11, 000,... } Terminologies State o Its purpose is to remember the relevant portion of the system’s history. Type Conventions for Symbols and Strings 1. states → q’s and p’s 2. q0 → initial state 3. 0, 1, a, b → input symbols 4. w, x, y, z → strings of input symbols The basic structure of a proof is easy: it is just a series of statements, each one being either ✓ An assumption or ✓ A conclusion, clearly following from an assumption or previously proved result. ▪ Direct Proof ▪ Proof by Contradiction ▪ Proof by Contrapositive ▪ If and only if ▪ Proof by Mathematical Induction  Informally, a state diagram that comprehensively captures all possible states and transitions that a machine can take while responding to a stream or sequence of input symbols. It consists of finite set of state and a set of transitions from state to state that occur on input symbols chosen from an alphabet Used in text processors, compilers and hardware design Recognizer for “Regular Languages”. Examples of Finite Automata 1. Software for designing and checking the behavior of digital circuits. 2. The compiler component that breaks the input text into logical units, such as identifiers, keywords and punctuation. 3. Software for scanning large bodies of text, such as collections of Web pages, to find occurrences of words, phrases, or other patterns. 4. Software for verifying systems of all types that have a finite number of distinct states, such as communications protocols or protocols for secure exchange of information. Examples of Finite Automata A finite automaton A finite automaton modeling modeling an on/off recognition of the word then switch Classes of Finite Automata 1. Deterministic Finite Automaton (DFA) * The automaton cannot be in more than one state at any one time. * For each input symbol in , there is exactly one transition of each state (possibly back to the state itself). * It does not accept empty strings. 2. Nondeterministic Finite Automaton (NFA) * The automaton may be in several states at once. * It allows zero, one or more transitions for every input symbol. * It accepts empty strings. 1. State Diagram (or Transition Graph) A transition graph is a directed graph in that the vertices represent the internal states of the automaton, and the edges represent the transitions. The labels on the vertices are the names of the internal states, while the labels on the edges are the current values of the input symbols. The vertices of the graph correspond to the state of the FA. If there is a state q to p on input a, then there is an arc labeled "a" from state q to p. The FA accepts a string X if the sequence of transition corresponding to the symbols of X from the start state leads to an accepting state. 2. State Table (or Transition Table) 3. Transition Function →  (set of states, set of input alphabet) Formal Definition of a DFA DFA is defined by the 5-tuple: { Q, , , q0, F } where: Q → a finite set of states ∑ → a finite set of input symbols (alphabet) q0 → a start state F → set of final states δ → a transition function, which is a mapping between Q x ∑ → Q and takes as arguments a state and an input symbol and returns a state. (i.e., (q0, x) = q1) What does a DFA do on reading an input string? Input: a word w in ∑* Question: Is w acceptable by the DFA? Steps: Start at the “start state” q0 For every input symbol in the sequence w do Compute the next state from the current state, given the current input symbol in w and the transition function If after all symbols in w are consumed, the current state is one of the final states (F) then accept w; Otherwise, reject w. Dead State Are those non final state which transits in itself for all input symbol. Example 1: Build a DFA for the following language: L = {w | w is a binary string that contains 01 as a substring} Steps for building a DFA to recognize L: ∑ = {0,1} Decide on the states: Q Designate start state and final state(s) δ: Decide on the transitions: Final states == same as “accepting states” Other states == same as “non-accepting states” Solution on next slide  1 0,1 0 0 1 start q0 q1 q2 Final state Example 2: Design a DFA, M which accepts the language: L(M) = {w  (a, b)* :w does not contain three consecutive b’s)} Let M = (Q, ∑, δ, q0 , F ) δ is defined as follows: δ where: Q = {q0, q1, q2, q3} ∑ = {a, b} q0 is the initial state F = {q0, q1 q2,} Solution on next slide State Diagram State Table Transition Function δ(q0, a) = q0 δ(q0, b) = q1 δ(q1, a) = q0 δ(q1, b) = q2 δ(q2, a) = q0 δ(q2, b) = q3 δ(q3, a) = q3 δ(q3, b) = q3 Example 3: Determine the DFA schematic for : M = (Q, ∑, δ, q1 , F ) where: δ is defined as: Q = {q1, q2, q3} δ ∑ = {0,1} q1 is the start state F = {q2} Solution on next slide L={w | w contains at least one 1 and an even number of 0’s follow the last 1} Example 4: Sketch the DFA given: M= ({q1, q2}, {0, 1}, δ ,q1, {q2}) and δ is given by: δ(q1, 0) = q1 δ(q1, 1) = q2 δ(q2, 0) = q1 δ(q2, 1) = q1 Solution on next slide Example 5: Design a DFA, the language recognized by the Automaton being L= {a b: n n≥0} Solution on next slide Let M = ( Q, , q0, , F ) be a DFA and w  *. To describe the behavior of M on w, we extend the transition function  to apply to a state and a string rather than a state and an input symbol. The extended transition function for M, written as * is the function: defined recursively as follows: (i) *(q, λ) = q for all q  Q (ii) *(q, wa) = (*(q, w),a) for all w  *, a   and q  Q Note that for any a  : Thus, * extends  from a single letter to a string.  Let w = abba  *, determine if the string abba is accepted or rejected by the DFA. Formative Assessment 4 Check Canvas