NFA

• NON-DETERMINISTIC FINITE AUTOMATAS (NFAs), informally

  • Similar to a DFA
  • However, it can be in more than one state at the same time
  • From a state, with an input, it can go to various states
  • For instance, when the automaton is used to search a particular string in a text, it is helpful to guess that we are at the beginning of that string and use a sequence of states to do nothing but check if the string appears, character by character
  • In the end, it is enough that one of the states reached be an accept state
• EXAMPLE

  
• INFORMALLY PROCESSING IN AN NFA

  • Lets consider the input 10101
  • In order to avoid guessing, we analyze all the alternatives in parallel
  • Simpler FA but requiring a higher computing complexity
  • 10101 is accepted as we reached a final state, q3, in one of the paths/threads
  • When theres no transitions from a given state/input, that thread just dies

  
• DEFINITION OF AN NFA

  A) states

  B) input

  C) start state

  D) final

  E) accepting

  F) transition

  G) state

  H) input

  I) value

  J) set

  K) states

  L) single state

  
• NFA TRANSITION TABLE EXAMPLES

  
• EXTENDED TRANSITION FUNCTION

  A) x

  
• EXAMPLE

  
• LANGUAGE OF AN NFA

  A) sequence

  B) next

  C) w

  D) start state

  E) accepting state

  F) nonaccepting

  G) not

  H) strings

  I) accepting state

  
• NFA - DFA EQUIVALENCE

  A) 2^n

  B) eliminated

  
• EXAMPLE (NFA - DFA EQUIVALENCE)

  
• WITH REACHABLE STATES ONLY

  
• EXAMPLE

  
• COMPUTATIONAL COST

  • The worst case for the subset construction is when we need an exponential number of states for the DFA:

  2n, including the dead state, for an NFA with n states

  • However, in many cases the number of states of the DFA is not too higher than the number of states of the NFA
  • Indeed, we can apply the NFA to DFA conversion starting by the start state and considering only the reachable states
• DEAD STATES

  A dead state is a non-accepting state with self transitions for all the symbols of the alphabet

  -It is used to capture errors in a DFA

  -If the automaton has a maximum of one transition for each state/alphabet symbol, even if it is not complete, it can be considered a DFA (sometimes referred as an incomplete DFA): to be a DFA it is only needed to add the dead state (with self transitions) to where all the missing transitions will go
• THEOREM NFA-DFA

  A) L(D)=L(N)

  
• THEOREM OF THE DFA - NFA LANGUAGE

  A) DFA

  B) NFA