dfa_state_complexity_empty
For any alphabet α, the deterministic state complexity of the empty language 0 is at most 1.
Statement
theorem dfa_state_complexity_empty (α : Type*) : dfa_state_complexity (0 : Language α) ≤ 1
- Source
- folklore
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- dfa_state_complexityThe deterministic state complexity of a language L is the minimum number of states in any deterministic finite automaton (DFA) with finite…
Read back from the Lean
For every type α, the DFA state complexity of the empty language (0 : Language α) is less than or equal to 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The deterministic state complexity of a language is defined as the infimum of the number of states of any DFA accepting it. To show this is at most 1 for the empty language, it suffices to construct a 1-state DFA accepting it. The proof exhibits an automaton on the single state `Unit` with no accepting states, which vacuously accepts no words and therefore accepts the empty language.
It suffices to show that the one-state DFA with no accept states accepts the empty language.
The state complexity of the empty language is defined as the infimum of the number of states of any DFA accepting it. By `Nat.sInf_le`, exhibiting a DFA with 1 state that accepts the empty language upper-bounds the infimum by 1. We provide a DFA whose state space is the singleton type `Unit` (which has cardinality 1 by `Fintype.card_unit`), with start state `()`, trivial transition function mapping every state and alphabet symbol to `()`, and empty set of accept states `∅`.
uses
Nat.sInf_le,Fintype.card_unitapply Nat.sInf_le refine ⟨Unit, inferInstance, ⟨fun _ _ => (), (), ∅⟩, Fintype.card_unit, ?_⟩
The constructed DFA accepts no words, matching the empty language.
By language extensionality (`ext x`), it suffices to show that an arbitrary word x is accepted if and only if it belongs to the empty language (0). By `DFA.mem_accepts`, x is accepted if and only if the DFA terminates in an accept state. Since the set of accept states is empty, this condition is false for every word, which matches membership in the empty language.
uses
DFA.mem_acceptsext x simp [DFA.mem_accepts]
Nat.sInf_le- If a natural number m belongs to a set s of natural numbers, then the infimum of s is at most m.
Fintype.card_unit- The singleton type Unit has cardinality 1.
DFA.mem_accepts- A word x belongs to the language accepted by a DFA M if and only if the state reached after processing x is an accept state.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The empty language over any alphabet has DFA state complexity at most 1. -/theorem dfa_state_complexity_empty (α : Type*) : dfa_state_complexity (0 : Language α) ≤ 1 := by apply Nat.sInf_le refine ⟨Unit, inferInstance, ⟨fun _ _ => (), (), ∅⟩, Fintype.card_unit, ?_⟩ ext x simp [DFA.mem_accepts]