Welcome guest
You're not logged in.
264 users online, thereof 1 logged in

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.

## 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 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]