Monday 24 June 2013

Nondeterministic Finite Automata, NFA

 Important! nondeterministic has nothing to do with random,
            nondeterministic implies parallelism.

 The difference between a DFA and a NFA is that the state transition
 table, delta, for a DFA has exactly one target state but for a NFA has
 a set, possibly empty (phi), of target states. Think parallel.

 Example of a NFA, Nondeterministic Finite Automata given
 by a) Machine Definition  M = (Q, sigma, delta, q0, F)
    b) Equivalent regular expression
    c) Equivalent state transition diagram
    and example tree of states for input string 0100011
    and an equivalent DFA, Deterministic Finite Automata for the
    first 3 states.

 a) Machine Definition  M = (Q, sigma, delta, q0, F)

 Q = { q0, q1, q2, q3, q4 } the set of states
 sigma = { 0, 1 }           the input string alphabet
 delta                      the state transition table
 q0 = q0                    the starting state
 F = { q2, q4 }             the set of final states (accepting when in
                            this state and no more input)

                          inputs
         delta    |    0    |    1    |
         ---------+---------+---------+
              q0  | {q0,q3} | {q0,q1} |
              q1  |   phi   |   {q2}  |
    states    q2  |   {q2}  |   {q2}  |
              q3  |   {q4}  |   phi   |
              q4  |   {q4}  |   {q4}  |

              ^       ^         ^
              |       |         |
              |       +---------+-- a set of states, phi means empty set
              +-- every state must be listed

 b) The equivalent regular expression is  (0+1)*(00+11)(0+1)*
 This NFA represents the language L = all strings over {0,1} that
 have at least two consecutive 0's or 1's.



         c) Equivalent  NFA  state transition diagram.


Note that state q3 does not go anywhere for an input of 1.
We use the terminology that the path "dies" if in q3 getting an input 1.

The tree of states this NFA is in for the input  0100011

                                                       input
                            q0
                           /  \                          0
                         q3    q0
                        dies  /  \                       1
                            q1    q0
                           dies  /  \                    0
                               q3    q0
                              /     /  \                 0
                            q4    q3    q0
                           /     /     /  \              0
                         q4    q4    q3    q0
                        /     /     dies  /  \           1
                      q4    q4          q1    q0
                     /     /           /     /  \        1
                   q4    q4          q2     q1   q0

                   ^     ^           ^
                   |     |           |
             accepting paths in NFA tree


 Construct a DFA equivalent to the NFA above using just the first
 three rows of delta (for brevity, consider q3 and q4 do not exists).

 The DFA machine is M' = (Q', sigma, delta', q0', F')
 The set of states is
 Q' = 2**Q, the power set of Q = { phi, {q0}, {q1}, {q2}, {q0,q1}, {q0,q2},
                                   {q1,q2}, {q0,q1,q2} }

 Note the big expansion: If a set has n items, the power set has 2^n items.

 Note: read the eight elements of the set Q' as names of states of M'
       OK to use [ ]  in place of { } if you prefer.

 sigma is the same  sigma = { 0, 1}
 The state transition table delta' is given below
 The starting state is set containing only q0  q0' = {q0}

 The set of final states is a set of sets that contain q2
 F' = { {q2}, {q0,q2}, {q1,q2}, {q0,q1,q2} }
 
  
Algorithm for building delta' from delta:

  The delta' is constructed directly from delta.
  Using the notation f'({q0},0) = f(q0,0) to mean:
    in delta' in state {q0} with input 0  goes to the state
    shown in delta with input 0.  Take the union of all such states.
  Further notation, phi is the empty set so phi union the set A is
  just the set A.

  Some samples: f'({q0,q1},0) = f(q0,0) union f(q1,0) = {q0}
                f'({q0,q1},1) = f(q0,1) union f(q1,1) = {q0,q1,q2}
                f'({q0,q2},0) = f(q0,0) union f(q2,0) = {q0,q2}
                f'({q0,q2},1) = f(q0,1) union f(q2,1) = {q0,q1,q2}

                          sigma
         delta    |    0    |    1    |  simplified for this construction
         ---------+---------+---------+
              q0  |   {q0}  | {q0,q1} |
    states    q1  |   phi   |   {q2}  |
              q2  |   {q2}  |   {q2}  |


                               sigma
         delta'    |     0       |      1      |
         ----------+-------------+-------------+
             phi   |    phi      |     phi     | never reached
            {q0}   |   {q0}      |   {q0,q1}   |
 states     {q1}   |    phi      |     {q2}    | never reached
 Q'         {q2}   |   {q2}      |     {q2}    | never reached
          {q0,q1}  |   {q0}      | {q0,q1,q2}  |
          {q0,q2}  | {q0,q2}     | {q0,q1,q2}  |
          {q1,q2}  |   {q2}      |     {q2}    | never reached
        {q0,q1,q2} | {q0,q2}     | {q0,q1,q2}  |

  Note: Some of the states in the DFA may be unreachable yet
        must be specified. Later we will use Myhill minimization.


  DFA (not minimized) equivalent to lower branch of NFA above.

  The sequence of states is unique for a DFA, so for the same input as
  above  0100011 the sequence of states is
  {q0}  0  {q0}  1  {q0,q1} 0  {q0}  0  {q0}  0  {q0}  1  {q0,q1}
        1 {q0,q1,q2}

  This sequence does not have any states involving q3 or q4 because just
  a part of the above NFA was converted to a DFA. This DFA does not
  accept the string  00  whereas the NFA above does accept  00.



Given a NFA and one or more strings, determine if the string(s)
are accepted by the NFA. This may be error prone and time
consuming to do by hand. Fortunately, there is a program
available to do this for you.

On linux.gl.umbc.edu  do the following:

  ln -s /afs/umbc.edu/users/s/q/squire/pub/nfa nfa
  cp    /afs/umbc.edu/users/s/q/squire/pub/download/fig2_7.nfa .
  nfa < fig2_7.nfa    # or  nfa < fig2_7.nfa > fig2_7.out

You can code a Machine Definition     into a data file for simulation

 Q = { q0, q1, q2, q3, q4 }
 sigma = { 0, 1 }                        // fig2_7.nfa
 delta                      
 q0 = q0                                 start q0
 F = { q2, q4 }                          final q2
                                         final q4
                    sigma
   delta    |    0    |    1    |        q0 0 q0
   ---------+---------+---------+        q0 0 q3
        q0  | {q0,q3} | {q0,q1} |        q0 1 q0
        q1  |   phi   |   {q2}  |        q0 1 q1
states  q2  |   {q2}  |   {q2}  |        q1 1 q2
        q3  |   {q4}  |   phi   |        q2 0 q2
        q4  |   {q4}  |   {q4}  |        q2 1 q2
                                         q3 0 q4
                                         q4 0 q4
                                         q4 1 q4

                                         enddef

                                         tape 10101010 // reject
                                         tape 10110101 // accept
                                         tape 10100101 // accept
                                         tape 01010101 // reject

No comments:

Post a Comment