dfa_state_complexity
deforiginal
The deterministic state complexity of a language L is the minimum number of states in any deterministic finite automaton (DFA) with finite state set in Type that recognizes L.
Statement
noncomputable def dfa_state_complexity {α : Type*} (L : Language α) : ℕ
- Related work
- folklore
- Verified
- 24 Oct 2026
- Axioms
- none listed
- Used by 1
- dfa_state_complexity_emptyFor any alphabet α, the deterministic state complexity of the empty language 0 is at most 1.
Read back from the Lean
Given a type α and a formal language L over α (i.e., L : Set (List α)), dfa_state_complexity L is the infimum in ℕ of the set of all natural numbers k such that there exists a type σ : Type with a Fintype instance and a deterministic finite automaton M : DFA α σ satisfying Fintype.card σ = k and M.accepts = L.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The deterministic state complexity of a language is the minimum number of states in a DFA accepting it. -/ noncomputable def dfa_state_complexity {α : Type*} (L : Language α) : ℕ := sInf { k : ℕ | ∃ (σ : Type) (_ : Fintype σ) (M : DFA α σ), Fintype.card σ = k ∧ M.accepts = L }