For every epsilon non-deterministic finite automaton $\epsilon$-NFA there is a deterministic finite automaton DFA accepting the same language.

In other words, the class $\mathcal L(\epsilon-\operatorname{NFA})$ of all languages accepted by any $\epsilon$-NFA equals the class $\mathcal L(\operatorname{DFA})$ of all languages accepted by any DFA, formally

$$\mathcal L(\epsilon-\operatorname{NFA})=\mathcal L(\operatorname{DFA}).$$

| | | | | created: 2020-05-21 18:39:29 | modified: 2020-05-21 18:54:43 | 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