- First, reduce a given $\epsilon$-NFA to an NFA according to theorem about the reduction of epsilon-nfa to nfa.
- Now, reduce the resulting NFA to a DFA according to the Rabin-Scott theorem.
- This shows the set inclusion $\mathcal L(\epsilon-\operatorname{NFA})\subseteq\mathcal L(\operatorname{DFA}).$
- The other set inclusion $\mathcal L(\operatorname{DFA})\subseteq\mathcal L(\epsilon-\operatorname{NFA})$ is trivial.

q.e.d

| | | | created: 2020-05-21 18:51:43 | modified: 2020-05-21 18:54:59 | by: | references: [1086], [7895]

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

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