Automata Definitions

(Greek letters are written out so this can be read as plain text.)

Contents

  • Machine
  • Finite Automata, FA, DFA, FSM
  • Nondeterministic Finite Automata, NFA
  • Pushdown Automata, PDA
  • Turing Machine
  • Universal Turing Machine
  • Church Turing Hypothesis
  • Languages accepted by polynomial time Turing Machines, P
  • Nondeterministic Polynomial time Turing Machines, NP
  • Moore Machine
  • Mealy Machine
  • Machine Equivalences
  • Machine to Language Equivalences
  • Equivalent Computational Power
  • Other Links
  • Machine

      A general term for an automata.
      A machine could be a Turing Machine, a pushdown automata, 
      a finite state machine or any other restricted version of a Turing machine.
    

    Finite Automata also called a Finite State Machine, FA, DFA or FSM

      M = (Q, Sigma, delta, q0, F) is a definition of a Finite Automata.
      To be fully defined the following must be provided:
    
      Q a finite set of states often called q0, q1, ... , qn or s0, s1, ... , sn.
      There is no requirement, in general, that every state be reachable.
    
      sigma a finite input  alphabet
    
      delta a transition function mapping Q cross sigma to Q. delta is typically
      given as a table with all states listed on the right, input symbols
      listed across the top and next state in the table:
    
                                           input
       delta, the transition table
                                       |  0  |  1  |
                                   ----+-----+-----+
                                   s0  |  s1 | s2  |
                                   ----+-----+-----+
                          state    s1  |  s2 | s0  |
                                   ----+-----+-----+
                                   s2  |  s2 | s1  |
                                   ----+-----+-----+
    
      When the transition table, delta, has all single entries, the machine
      may be refereed to as a Deterministic Finite Automata, DFA.
    
      There is no requirement, in general, that every entry in the table must
      contain a state.  If a machine tries to go to an empty table entry it
      "crashes". The remainder of the input, if any, is unread. The machine
      does not accept and can not possibly be in a final state.
      When every state/input pair has at most one target state, the automata
      is called deterministic. (See below for definition of nondeterministic.)
    
      q0 the initial state from the set Q.
      By definition this is the state the automata is in when it starts.
      The automata gets the first symbol from the input, then goes from
      the starting state to the state designated by the transition function. 
    
      F a set of final states from the set Q.
      Final states are also known as accepting states.
      The machine stops after the last input symbols is read and the
      corresponding state transition occurs. If the machines state when
      stopped is in F then the machine is said to accept the input string.
      F can be a null set in which case only the empty language is accepted.
      There is no requirement, in general, that any final state be reachable.
    
      A machine defines a language, the set of all strings accepted by
      the machine. This language is usually denoted  L(M).  The machine that
      accepts a language L  is usually denoted  M(L).
    
      There is a Finite Automata, as defined here, for every Regular Language and
      a Regular Language for every Finite Automata.
      
      Another common way to define a Finite Automata is via a diagram.
      The states are shown as circles, often unlabeled, the initial state has
      an arrow pointing to it, the final states have a double circle,
      the transition function is shown as directed arcs with the input
      symbol(s) on the arc.
    

    Nondeterministic Finite Automata, NFA

      Note: This has nothing to do with randomness!
    
      M = (Q, sigma, delta, q0, F) is the same as for deterministic finite automata
      above with the exception that delta can have sets of states.
    
      delta for a nondeterministic machine looks like:
    
    
                                               input
          delta the transition table
                                       |  0      |  1      |
                                   ----+---------+---------+
                                   s0  | {s1,s2} | {s2}  |
                                   ----+---------+---------+
                          state    s1  | {s0,s2} | phi     |
                                   ----+---------+---------+
                                   s2  |  phi    | {s1}    |
                                   ----+---------+---------+
    
      A string is accepted if any sequence of transitions ends in a Final state.
      There could be more than one sequence of transitions that end in a
      Final state.
    
      Think of each transition that has more than one state as causing a tree
      to branch. All branches are in some state and all branches transition on
      every input.  Any branch that reaches phi, the null or nonexistent state,
      terminates.
    
      Any NFA can be converted to a DFA but the DFA may require exponentially
      more states than the NFA.
    
    

    Push Down Automata, PDA

    
     Push Down Automata, PDA, are a way to represent the language class called
     Context Free Languages, CFL, covered above. By themselves PDA's are not
     very important but the hierarchy of Finite State Machines with
     corresponding Regular Languages, PDA's with corresponding CFL's and
     Turing Machines with corresponding Recursively Enumerable Sets (Languages),
     is an important concept.
    
     The definition of a Push Down Automata is:
     M = (Q, Sigma, Gamma, delta, q0, Z0, F)  where
     Q = a finite set of states including q0
     Sigma = a finite alphabet of input symbols (on the input tape)
     Gamma = a finite set of push down stack symbols including Z0
     delta = a group of nondeterministic transitions mapping
             Q x (Sigma union {epsilon}) x Gamma to finite sets of Q x Gamma star
     q0 = the initial state, an element of Q, possibly the only state
     Z0 = the initial stack contents, an element of gamma, possibly the only
          stack symbol
     F = the set of final, accepting, states but may be empty for a PDA
         "accepting on an empty stack"
    
     Unlike finite automata, the delta is not presented in tabular form.
     The table would be too wide.  Delta is a list of, nondeterministic,
     transitions of the form:
       delta(q,a,A) = { (qi,gammai), (qj,gammaj), ...}  where
       q is the current state,
       a is the input tape symbol being read, an element of Sigma union {epsilon}
       A is the top of the stack being read,
       The ordered pairs (q sub i, gamma sub i) are respectively the next state
       and the string of symbols to be written onto the stack. The machine
       is nondeterministic, meaning that all the pairs are executed causing
       a branching tree of PDA configurations. Just like the branching tree
       for nondeterministic finite automata except additional copies of the
       pushdown stack are also created at each branch.
    
     The operation of the PDA is to begin in state q0, read the symbol on the
     input tape or read epsilon. If a symbol is read, the read head moves
     to the right and can never reverse to read that symbol again.
     The top of the stack is read by popping off the symbol.
     Now, having a state, an input symbol and a stack symbol a delta transition
     is performed. If there is no delta transition defined with these three
     values the machine halts. If there is a delta transition with the (q,a,A)
     then all pairs of (state,gamma) are performed. The gamma represents a
     sequence of push down stack symbols and are pushed right to left onto
     the stack. If gamma is epsilon, no symbols are pushed onto the stack. Then
     the machine goes to the next state, q.
    
     When the machine halts a decision is made to accept or reject the input.
     If the last, rightmost, input symbol has not been read then reject.
     If the machine is in a final state accept.
     If the set of final states is empty, Phi, and the only symbol on the stack
     is Z0, then accept. (This is the "accept on empty stack" case)
    
    
     Now, using pictures we show the machines for DFA, PDA and TM
    
     +-------------------------+----------------- DFA, NFA, NFA epsilon
     | input string            |                  accepts Regular Languages
     +-------------------------+----------------- 
        ^ read, move right
        |
        |  +-----+
        |  |     |--> accept
        +--+ FSM |                   M = ( Q, Sigma,        delta, q0,    F)
           |     |--> reject
           +-----+
    
     +-------------------------+----------------- Push Down Automata
     | input string            |Z0  stack         accepts Context Free Languages
     +-------------------------+-----------------
        ^ read, move right      ^ read and write (push and pop)
        |                       |
        +-----------------------+
        |  +-----+
        |  |     |--> accept
        +--+ FSM |                   M = ( Q, Sigma, Gamma, delta, q0, Z0, F)
           |     |--> reject
           +-----+
    
     +-------------------------+-----------------  Turing Machine
     | input string            |BBBBBBBB ...       accepts Recursively Enumerable
     +-------------------------+-----------------  Languages
        ^ read and write, move left and right
        |
        |  +-----+
        |  |     |--> accept
        +--+ FSM |                   M = ( Q, Sigma, Gamma, delta, q0, B,  F)
           |     |--> reject
           +-----+
    
    
      An example of a language that requires the PDA to be a NPDA,
      Nondeterministic Push Down Automata,
      is L = { w wr | w in Sigma and wr is w written backwards }
    
    

    Turing Machine, TM

      A Turing machine, named after A. Turing, is defined by
      M = (Q, Sigma, Gamma, delta, q0, B, F)
      where
    
      Q     is a finite set of states (same as DFA)
      Gamma is a finite set of tape symbols
      B     is a symbol in Gamma is the blank, or space symbol
      Sigma is a subset of Gamma not including B, the input symbols
      delta is the transition function, next move table, that maps
            Q cross Gamma to Q cross Gamma cross {Left, Right}
      q0    is in Q and is the initial or starting state
      F     is a subset of Q, the final states.  After the last input symbol has
            been read and the tape is in the leftmost position,
            a string is accepted if M is in a final state.
    
      In this particular model, the tape is only unbounded on the right,
      filled with B's and fixed on the left at the first input symbol.
    
      Other models include a tape also unbounded on the left , symbols on the
      tape for "left-end" and "right-end", ability to write no symbol, ability
      to move {Left, Right or None}. These variations and many more are
      provably equivalent.  A Turing Machine that computes a value rather than
      recognizing a language, leave the computed value on the tape and halts.
    
      It is possible for a TM to never halt on some input strings that are not
      in the language it accepts or on input values for which it is not
      a complete function.
    
      The set of all Turing machines is countable.  Thus there exists real
      numbers that can not be accepted by any Turing machine.
    
      delta transition table might look like
    
    
    
                                                    input
       delta, the transition table
                                       |  0       |  1       |  b       |
                                   ----+----------+----------+----------+
                                   s0  | (s1,1,R) | (s2,0,L) | Phi      |
                                   ----+----------+----------+----------+
                          state    s1  | (s0,0,L) | Phi      | (s0,1,R) |
                                   ----+----------+----------+----------+
                                   s2  |  Phi     | (s1,1,R) | (s2,b,L) |
                                   ----+----------+----------+----------+
    
    
      A Turing machine may also have a nondeterministic transition table that
      has sets of entries. Every member of the set of a transition then
      continues operation in parallel, each with its own state and tape.
    
      Phi is the null or nonexistent state. If a TM enters the phi state it is
      "hung" and there is no indication to the outside world.  There is no
      accept and no reject output signal.  No further tape head movement
      occurs and no further symbols are read from the tape.
    
      Each "step" executed by a Turing machine does the following:
        The machine is in some state, q0 initially.
        The read/write head is positioned on some tape cell, initially leftmost.
        The pair (state q, input symbol a) select one cell in the delta
        transition table. e.g. delta(q,a) = (qi, b , R)
        The machine enters state qi, writes b onto the tape, moves right.
    
      The running time of a Turing machine is measured in number of steps
      and is usually related to the length of the input, the number of
      symbols on the initial tape.
    
    

    Universal Turing Machine, UTM

      It is possible to code the definition of every Turing machine as a string of
      characters.  
      A Universal Turing Machine is then a Turing machine that has on its input
      tape a definition of some Turing machine and a string.  The Universal
      Turing Machine simulates the Turing machine defined on its input tape and
      accepts the string on its input tape if and only if the simulated Turing
      machine would accept the string.
    
      One UTM can simulate another UTM that is simulating a TM with an input string.
      Etc. Etc. Etc.
    

    Church Turing Hypothesis

       See Computability Definitions 
    

    Languages accepted by polynomial time Turing Machines, P

      The Turing machine restricted to a number of moves bounded by a
      fixed polynomial in n, p(n), where n = |x|, n is the length of the
      input string.  The machine must accept all strings in a language in
      polynomial time in order to be in P.
      P is a set of languages, also called a class of languages.
    

    Nondeterministic Polynomial time Turing Machines, NP

      Change the deterministic delta transition table to a nondeterministic delta
      transition table and the TM represents a class of languages that are
      believed to be different from the language class P.
      NP is a set of languages, also called a class of languages.
    

    Moore Machine

      A Moore machine is defined as  M = (Q, sigma, Delta, delta, gamma, q0)
      Where Q, Sigma, delta and q0 are as defined for finite automata.
      Delta is the output alphabet.
      gamma is a mapping from Q to Delta.
    
    
     +-------------------------+ 
     | input string            |  Moore machine, no more powerful than DFA
     +-------------------------+
        ^ read, move right
        |
        |  +-----+
        |  |     |
        +--+ FSM |              M = ( Q, Sigma, Delta, delta, gamma, q0)
           |     |
           +-----+
             |
             v
          +-----------------------------
          | output tape alphabet Delta (May be same or vary from Sigma)
          +-----------------------------
    
      Example: Q= {q0, q1}  Sigma= {a, b}  Delta= {A, B}  gamma= q0->A, q1->B
    
          delta | a  | b  | gamma
          ------+----+----+------
            q0  | q1 | q0 | A
            q1  | q0 | q1 | B
    
              A            B  <--shows symbol written to output when entering state
            _____   a    _____
       --> / q0  \----->/ q1  \   and other connecting transitions like a DFA
           \_____/<---- \_____/
                     b
    
      This is a finite state machine that outputs a symbol on every state
      transition starting with gamma(q0) which is always output.
    
      Note there is no set F of final states. A Moore machine is equivalent to
      a DFA when Delta = {0, 1} and a zero output is interpreted as reject,
      while a 1 output is interpreted as accept and gamma maps final states
      to 1 and all other states to 0.
    
      A finite automata can only accept (last input symbol put machine in a final
      state) or reject an input string. A Moore machine is like a simple
      function where an input is processed and a result is produced.
    
      Moore machines are usually not based on NFA's because this would be like
      a multi valued function.  Some input could produce more than one output. 
    

    Mealy Machine

      A Mealy machine is defined as  M = (Q, sigma, Delta, delta, gamma, q0)
      using the definitions from the Moore machine with the exception that
      gamma maps Q cross Sigma to Delta.
      Delta is the output alphabet.
      Thus the output is a function of the state and the input symbol,
      written during the state transition.
      The difference from a Moore machine is the output being a function 
      of the transition rather than just a function of the sequence of states.
    
      The empty string as input produces an empty output.
    
    
     +-------------------------+ 
     | input string            |  Mealy machine, no more powerful than DFA
     +-------------------------+
        ^ read, move right
        |
        |  +-----+
        |  |     |
        +--+ FSM |              M = ( Q, Sigma, Delta, delta, gamma, q0)
           |     |
           +-----+
             |
             v
          +-----------------------------
          | output tape alphabet Delta (May be same or vary from Sigma)
          +-----------------------------
    
      Example: Q= {q0, q1}  Sigma= {a, b}  Delta= {A, B, C, D}  gamma is in delta
    
          delta |   a  |   b  
          ------+------+------
            q0  | q1A | q0C
            q1  | q0D | q1B
    
                       /--shows symbol written to output upon transition
            _____   a/A    _____
       --> / q0  \------->/ q1  \   and other connecting transitions state/output
           \_____/<------ \_____/
                     a/D
    
      Mealy machines are usually not based on NFA's because this would be like
      a multi valued function.  Some input could produce more than one output. 
    
      The proof that a Mealy machine and a DFA are equivalent, using gamma being
      a one for accept on transition to a final state, and gamma being zero
      otherwise, also needs a little effort to have a Mealy machine accept
      the null string, epsilon.
    
    

    Machine Equivalences

      The following machines are provably equivalent
      FA = DFA = NFA = NFA epsilon
      FA = two way FA (tape can move left, right, or not move)
      FA = Moore machine with output alphabet {0, 1} and state q accepting if and
           only if gamma(q)=1
      FA = Mealy machine with some technicalities
    
      TM = unrestricted grammar
      TM = lambda calculus
      TM = Post formal systems
      TM = NTM
      TM = TM with more tapes, write or not write, move or not move, etc.
    
      PDA not equal NPDA
    
    

    Machine to Language Equivalences

      FA        = regular languages
      PDA(NPDA) = context free languages
      TM        = recursively enumerable languages
    
    

    Various Equivalences

      The following group can have equivalent computational power
        partial recursive functions
        r.e. languages = recursively enumerable languages
        Turing machines that may not halt when input is not accepted
        unrestricted grammars
        lambda calculus
        Post Formal Systems
        computer programs in a reasonable language that may not halt on some input
        Chomsky type 0 languages
    
    
      The following group can have equivalent computational power
        total recursive functions
        recursive languages = rec
        Turing machines that halt on all inputs
        grammars that stop on all inputs
        lambda calculus with finite recursion
        computer programs that halt on all inputs
    
      The following group can have equivalent computational power
        context sensitive languages, CSL's
        context sensitive grammars, CSG's
        Chomsky type 1 languages
    
      The following group can have equivalent computational power
        context free languages, CFL's
        context free grammars, CFG's
        NPDA nondeterministic pushdown automata
        Chomsky type 2 languages
    
      The following group can have equivalent computational power
        regular expressions
        regular languages
        regular grammars
        deterministic and nondeterministic finite automata, DFA, NFA, NFA epsilon
        Chomsky type 3 languages
    
    

    Other Links

    Go to top

    Last updated 1/23/04