We have seen that the 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.

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})$.

- 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 or not 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).

| | | | | created: 2020-05-21 09:18:52 | modified: 2020-05-21 11:34:06 | by: *bookofproofs* | references: [1086], [7895]

[1086] **Erk, Katrin; Priese, Lutz**: “Theoretische Informatik”, Springer Verlag, 2000, 2. Auflage

[7895] **Hoffmann, Dirk**: “Theoretische Informatik, 3. Auflage”, Hanser, 2015