AFTD Auto-Formalizing Theoretical Domains

binary_extremizer_is_trim

theoremverified

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].

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

    lines 4–5

      intro q
      constructor
  2. 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.

    lines 6–10

    uses NFA.evalFrom_nil

      · by_cases hq : (q : ℕ) = 0
        · use []
          simp only [NFA.evalFrom_nil]
          change (q : ℕ) = 0
          exact hq
  3. 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.

    lines 11–19

    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
  4. 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.

    lines 20–25

    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]
  5. 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.

    lines 26–38

    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

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