We have seen that the non-deterministic finite automata [NFA]https://www.bookofproofs.org/branches/non-deterministic-finite-automata-nfa/ provide ways to simplify the diagrams of finite automata describing formal languages, as compared to the deterministic finite automata. DFA. The so-called epsilon non-deterministic finite automata $\epsilon$-NFA add yet another concept to the NFA allowing even more simplifications of the diagrams. However, the simplifications introduced by $\epsilon$-NFA will not substantially increase the set of languages that can be described as a whole. We will prove that every $\epsilon$-NFA can be reduced to a suitable deterministic finite automaton, just as it was the case for the usual NFA.

Definition: Epsilon Non-Deteriministic Finite Automaton ($\epsilon$-NFA)

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

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

The formal language $L(\epsilon-\operatorname{NFA})$ accepted by the $\epsilon$-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(\epsilon-\operatorname{NFA}):=\{\omega_i\in\Sigma^*, \omega_0\omega_1\ldots\omega_n\in\Sigma^*\mid \exists s_0\in S,\; q=\Delta(\ldots\Delta(\Delta(s_0,\omega_0),\omega_1),\ldots,\omega_n)\in F\}.$$

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


Corollaries: 1
Examples: 2
Proofs: 3
Theorems: 4

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