◀ ▲ ▶Branches / Theoretical-computer-science / Formal-languages / Corollary: Reduction of `$\epsilon$`-NFA to DFA

Corollary: Reduction of $\epsilon$-NFA to DFA

(related to Theorem: Reduction of $\epsilon$-NFA to NFA)

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

Table of Contents

Proofs: 1

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015