Models of Computation


DFA - Deterministic finite automaton

FAdo's Class: FAdo.fa.DFA

A deterministic finite automaton is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$ consisting of:


NFA - Nondeterministic finite automaton

FAdo's Class: FAdo.fa.NFA

A nondeterministic finite automaton is defined by a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ consisting of:

Where $2^Q$ is the power set of $Q$, i.e., the set of all subsets of $Q$. 

The NFA with $\epsilon$-moves replaces the transition function with one that allows the empty string as a possible input so that one has:


IDFA - Incomplete deterministic finite automaton

FAdo's Class: FAdo.fa.DFA

An incomplete deterministic finite automaton is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ consisting of:

  • A finite set of states $Q$
  • A finite set of input symbols $\Sigma$, called the alphabet
  • A transition function $\delta : Q \times \Sigma \to Q$, which is a partial function
  • A start state $q_0 \in Q$
  • A set of accepting states $F \subseteq Q$