AFTD Auto-Formalizing Theoretical Domains

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

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 }
See it in the graphDiscuss this resultChallenge it