The DFA are deterministic. It means that if a DFA reads in a state $c_i$ the symbol $\sigma_i$, the next state $c_{i+1}$ is fixed and pre-determined. There are also non-deterministic finite automata which can have many - or none - possible next states. A formal definition of such automata follows.

Definition: Non-deterministic Finite Automaton (NFA)

A non-deterministic finite automaton NFA) is a tuple $A=(C,\Sigma,\Delta,F,s_0)$, containing

We say that the NFA accepts an input word $\omega$ if and only if the NFA reaches a final state $q\in F$ after consuming $\omega,$ starting at $s_0\in S$.

The formal language $L(\operatorname{NFA})$ accepted by the NFA can be defined as a set of all words over the alphabet $\Sigma$, which can be consumed by the composition of the relation $\Delta$ with itself, starting from some state in $s_0\in S$, and ending at some state in $q\in F,$ formally: $$L(\operatorname{NFA}):=\{\sigma_0\sigma_1\ldots\sigma_n\in\Sigma^*\mid \exists s_0\in S,\; q=\Delta(\ldots\Delta(\Delta(s_0,\sigma_0),\sigma_1),\ldots,\sigma_n)\in F\}.$$

The class of all languages accepted by an NFA is denoted by $\mathcal L(\operatorname{NFA})$.


Applications: 1
Definitions: 2
Examples: 3 4
Proofs: 5 6 7
Theorems: 8 9

Thank you to the contributors under CC BY-SA 4.0!




  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
  2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015