Saturday, September 28, 2013

DFA & NFA

In the course "Formal Language", we learned about "DFA and NFA", and here's my study notes.

Reference

Finite Automaton

A finite automaton is a processor that has states and reads input, each input character potentially setting it into another state.
 In my opinion, we can see this as a finite state machine.

Deterministic Finite Automaton (1943)

A finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string. 'Deterministic' refers to the uniqueness of the computation.
In one state at a time.

Nondeterministic Finite Automaton (1959)

A finite state machine that (1)does not require input symbols for state transitions and (2)is capable of transitioning to zero or two or more states for a given start state and input symbol.
In more than one state at a time.

Difference between DFA and NFA


  • all transitions are uniquely determined
  • an input symbol is required for all state transitions
  • DFAs are easier to understand, but NFAs are generally smaller.