BranchesHistoryHelpLogin
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

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

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

Edit or AddNotationAxiomatic Method

This work was contributed under CC BY-SA 4.0 by:

This work is a derivative of:

Bibliography (further reading)

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

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