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

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

| | | | | created: 2020-05-21 12:34:44 | modified: 2020-05-21 18:41:51 | by: bookofproofs | references: [1086], [7895]

1.Proof: (related to "Reduction of $\epsilon$-NFA to NFA")

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

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