The Rabin–Scott subset construction (NFA to DFA)
ProvedFamousTheorems.rabin_scott_subset_construction_6cThe Rabin–Scott subset construction. For every nondeterministic finite automaton over an alphabet with state set , the deterministic automaton whose states are the sets of states of accepts the same language as .
Rabin and Scott introduced this construction in 1959. It shows that nondeterminism adds no power to finite automata: NFAs and DFAs recognise the same languages, the regular languages. The blow-up from to states is unavoidable in the worst case.
Formalization note. Mathlib's NFA.toDFA_correct. M.toDFA is the subset automaton, with states Set σ, start state the set of start states, and accepting states the sets meeting the accepting states of . accepts is the accepted language, a Language α.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem rabin_scott_subset_construction_6c {α σ : Type*} (M : NFA α σ) : M.toDFA.accepts = M.accepts := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `NFA.toDFA_correct`. Proof here reduces to that Mathlib result.