AFTD Auto-Formalizing Theoretical Domains

dfa_state_complexity_empty

theoremverified

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.

  1. 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 `∅`.

    lines 3–4

    uses Nat.sInf_le, Fintype.card_unit

      apply Nat.sInf_le
      refine ⟨Unit, inferInstance, ⟨fun _ _ => (), (), ∅⟩, Fintype.card_unit, ?_⟩
  2. 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.

    lines 5–6

    uses DFA.mem_accepts

      ext 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

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