binary_extremizer_is_trim
For every positive natural number n, the binary extremizer NFA binary_extremizer_nfa n is trim: every state is reachable from the start state and can reach the accepting state.
Statement
theorem binary_extremizer_is_trim (n : ℕ) (hn : 1 ≤ n) :
nfa_is_trim (binary_extremizer_nfa n)- Source
- arXiv:2610.08525, Stronger bounds on the degree of ambiguity of finite automata
- Verified
- 29 Oct 2026
- Axioms
Quot.soundpropext- Built on 2
- binary_extremizer_nfaFor each n, binary_extremizer_nfa n is the NFA over alphabet Fin 2 with states Fin n, unique initial state 0, unique accepting state n -…
- nfa_is_trimAn NFA M is trim if every state q is reachable from the start states by some word and co-reachable (can reach an accept state by some word).
Read back from the Lean
For any natural number $n \ge 1$, the nondeterministic finite automaton binary_extremizer_nfa n is trim (nfa_is_trim); that is, every state $q \in \mathrm{Fin}\ n$ is both reachable from the start state set (there exists a word $w$ such that $q \in \mathrm{evalFrom}\ \mathrm{start}\ w$) and co-reachable / productive (there exists a word $w$ and an accept state $t$ such that $t \in \mathrm{evalFrom}\ \{q\}\ w$).
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 proof shows that the binary extremizer NFA is trim by demonstrating that every state q is both accessible from the start state 0 and coaccessible to the accepting state n - 1. Because the transition relation allows an edge from p to q' whenever p < q', any state q is either already the start state 0 (reached by the empty word) or reachable from 0 in one step via [0]. Symmetrically, q is either already the accepting state n - 1 (coaccessible via the empty word) or reaches n - 1 in one step via [0].
To prove the NFA is trim, it suffices to show that an arbitrary state q is both reachable from the start state and can reach an accepting state.
By definition, an NFA is trim if every state is accessible from the start set and coaccessible to the accept set. Introducing an arbitrary state q and applying constructor splits the goal into these two reachability requirements.
intro q constructor
If q = 0, then q is reachable from the start state using the empty word.
The start set of the automaton consists of states with value 0. When q = 0, q is already in the start set, and evaluating on the empty word leaves the state set unchanged by NFA.evalFrom_nil.
uses
NFA.evalFrom_nil· by_cases hq : (q : ℕ) = 0 · use [] simp only [NFA.evalFrom_nil] change (q : ℕ) = 0 exact hq
If q ≠ 0, then q is reachable from the start state 0 using the word [0].
Since 1 ≤ n, the state 0 is valid and belongs to the start set. Because q ≠ 0, we have 0 < q. The automaton's step relation allows a transition from p to q whenever p < q (regardless of the input symbol), so reading symbol 0 transitions from 0 to q. Using NFA.evalFrom_singleton, NFA.stepSet, and Set.mem_iUnion, the one-step reachability reduces to 0 < q, which omega resolves.
uses
NFA.evalFrom_singleton,NFA.stepSet,Set.mem_iUnion· use [0] simp only [NFA.evalFrom_singleton, NFA.stepSet, Set.mem_iUnion] refine ⟨⟨0, hn⟩, ?_, ?_⟩ · change (⟨0, hn⟩ : Fin n).1 = 0 rfl · change (⟨0, hn⟩ : Fin n).1 < (q : ℕ) ∨ _ dsimp left omega
If q + 1 = n, then q reaches an accepting state using the empty word.
The accepting states are those satisfying t + 1 = n. When q + 1 = n, q itself is an accepting state. By NFA.evalFrom_nil and Set.mem_singleton, evaluating from {q} on the empty word contains q, which is accepting.
uses
NFA.evalFrom_nil,Set.mem_singleton· by_cases hq : (q : ℕ) + 1 = n · use [] refine ⟨q, ?_, ?_⟩ · change (q : ℕ) + 1 = n exact hq · simp only [NFA.evalFrom_nil, Set.mem_singleton]
If q + 1 ≠ n, then q reaches the accepting state n - 1 using the word [0].
Since q < n and q + 1 ≠ n, linear arithmetic implies q < n - 1. The state n - 1 is in the accept set because (n - 1) + 1 = n. The automaton's transition relation permits a step from q to n - 1 because q < n - 1. Unfolding the evaluation on [0] with NFA.evalFrom_singleton, NFA.stepSet, and Set.mem_iUnion, the inequality q < n - 1 is verified by omega using q.is_lt.
uses
NFA.evalFrom_singleton,NFA.stepSet,Set.mem_iUnion· use [0] have htn : n - 1 < n := by omega refine ⟨⟨n - 1, htn⟩, ?_, ?_⟩ · change (⟨n - 1, htn⟩ : Fin n).1 + 1 = n dsimp omega · simp only [NFA.evalFrom_singleton, NFA.stepSet, Set.mem_iUnion] refine ⟨q, by simp, ?_⟩ change (q : ℕ) < (⟨n - 1, htn⟩ : Fin n).1 ∨ _ dsimp left have : (q : ℕ) < n := q.is_lt omega
NFA.evalFrom_nil- Evaluating an NFA from a set of states S on the empty word yields S.
NFA.evalFrom_singleton- Evaluating an NFA from a set of states S on a single symbol a is equal to the one-step transition set from S on a.
NFA.stepSet- The set of states reachable in a single transition on an input symbol from any state in a given set.
Set.mem_iUnion- An element belongs to an indexed union of sets if and only if it belongs to at least one set in the family.
Set.mem_singleton- An element belongs to the singleton set containing only itself.
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 binary extremizer automaton is trim for every n ≥ 1. -/theorem binary_extremizer_is_trim (n : ℕ) (hn : 1 ≤ n) : nfa_is_trim (binary_extremizer_nfa n) := by intro q constructor · by_cases hq : (q : ℕ) = 0 · use [] simp only [NFA.evalFrom_nil] change (q : ℕ) = 0 exact hq · use [0] simp only [NFA.evalFrom_singleton, NFA.stepSet, Set.mem_iUnion] refine ⟨⟨0, hn⟩, ?_, ?_⟩ · change (⟨0, hn⟩ : Fin n).1 = 0 rfl · change (⟨0, hn⟩ : Fin n).1 < (q : ℕ) ∨ _ dsimp left omega · by_cases hq : (q : ℕ) + 1 = n · use [] refine ⟨q, ?_, ?_⟩ · change (q : ℕ) + 1 = n exact hq · simp only [NFA.evalFrom_nil, Set.mem_singleton] · use [0] have htn : n - 1 < n := by omega refine ⟨⟨n - 1, htn⟩, ?_, ?_⟩ · change (⟨n - 1, htn⟩ : Fin n).1 + 1 = n dsimp omega · simp only [NFA.evalFrom_singleton, NFA.stepSet, Set.mem_iUnion] refine ⟨q, by simp, ?_⟩ change (q : ℕ) < (⟨n - 1, htn⟩ : Fin n).1 ∨ _ dsimp left have : (q : ℕ) < n := q.is_lt omega