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
- a finite set $C$ of conditions (or states),
- a finite input alphabet $\Sigma$,
- the state transition relation $\Delta\subseteq (C\times\Sigma^*)\times C$,
- the set of final states $F\subseteq C$, and
- the starting state $s_0\in C.$
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})$.
Notes
- The $\epsilon$-NFA is an acceptor since it has no output, only an input (just as it was the case for the DFA and the NFA).
- Unlike in the case of a usual NFA, the transition relation $\Delta$ of an $\epsilon$-NFA takes a pair $(s_i,\omega_i)$ as input, where $\omega_i$ can be a whole word in $\Sigma^*$, including the empty word $\epsilon\in\Sigma^*.$
- Note the difference: In the case of a usual NFA, the input was $(s_i,\sigma_i)$, where $\sigma_i$ could be only a symbol in $\Sigma$. Therefore, the $\epsilon$-NFA can do a transition from one state to another also with a whole word (including $\epsilon$). Its transitions in a diagram (when we draw a diagram for the $\epsilon$-NFA) can be labeled with whole words, not only symbols, including $\epsilon$.
- Another important difference is that $\epsilon$ can be excepted even if the starting state is not one of the final states.
- Whether an $\epsilon$-NFA can start with an input $\omega$, depends on this word $\omega$ and the definition of the transition relation $\Delta$ for the pair of values $(s_0,\omega)$. If that transition relation $\Delta$ is not defined for this pair, the $\epsilon$-NFA cannot start accepting the word, unless (!) $\Delta$ is defined for the input $(s_0,\epsilon).$ This is because $\omega=\epsilon\omega$, and the $\epsilon$-NFA could start accepting $(s_0,\omega)$ by first changing its state from $s_0$ to $s_1$ by consuming the empty word and then start to accept $\omega$ from the state $s_1$.
- Similarly to a usual NFA, $\Delta$ can be any relation and does not have to be left-total nor right-unique (like it was the case for the function $\delta$ in a DFA). This means that the new state $\Delta(s_0,\omega_0)$ is either necessarily defined for all possible inputs, nor determined. Potentially, there might be many outcomes in the $i$th step of $\Delta(s_i,\omega_i)$ or none.
- The only accepted words $\omega$ are concatenations of (empty or non-empty other words) $\omega_0\omega_1\ldots \omega_{n-1}$ leading to a state $s_n\in F.$
- Non-excepted words will make the $\epsilon$-NFA get stuck in a loop at some non-final state, or the $\epsilon$-NFA won't even start at all (similarly as for the NFA).
Mentioned in:
Corollaries: 1
Examples: 2
Proofs: 3
Theorems: 4
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
References
Bibliography
- Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
- Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015
