A deterministic finite state automaton (DFSA) is defined as a quintuple
, where:
  Q | [ initial state] |
| Q | [ finite set of states ] |
F  Q | [ subset of Q of final states ] |
 | [ finite set of symbols ] |
 | [ finite set of transitions between states ] |
A nondeterministic finite state automaton (NFSA) is defined as a quintuple
, where:
|
Q | [ initial state] |
| Q | [ finite set of states ] |
|
F Q | [ subset of Q of final states ] |
|
| [ finite set of symbols ] |
 | [ finite set of transitions between a state and a set of states ] |
Corresponding to the similar situation with regular grammars, for every NDFSA there is a DFSA which accepts the same language.