◀ ▲ ▶Branches / Theoretical-computer-science / Formal-languages / Theorem: Reduction of NFA to DFA (Rabin-Scott Theorem)

The examples of nfa":bookofproofs$8502 give rise to the question, whether the class $\mathcal L(\operatorname{NFA})$ of all languages accepted by any NFA is bigger than the class $\mathcal L(\operatorname{DFA})$ of all languages accepted by any DFA, due to the non-determinism of the NFA, as compared to the determinism of the DFA.

This question has been answered by Michael Rabin (1931 - ) and Dana S. Scott (1932 - ) in 1959 in Finite Automata and Their Decision Problems.

Theorem: Reduction of NFA to DFA (Rabin-Scott Theorem)

For every non-deterministic finite automaton. NFA there is a deterministic finite automaton. DFA accepting the same language. In other words, the class $\mathcal L(\operatorname{NFA})$ of all languages accepted by any NFA equals the class $\mathcal L(\operatorname{DFA})$ of all languages accepted by any DFA, formally

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

Table of Contents

Proofs: 1

Mentioned in:

Applications: 1
Proofs: 2 3

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