Theorem: Reduction of $\epsilon$-NFA to NFA

For every epsilon non-deterministic finite automaton $\epsilon$-NFA there is a non-deterministic finite automaton. NFA 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{NFA})$ of all languages accepted by any NFA, formally

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

Corollaries: 1 Proofs: 1

Applications: 1
Proofs: 2

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




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