AFTD Auto-Formalizing Theoretical Domains

binary_extremizer_nfa

deforiginal

For 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 - 1, both an a-transition and a b-transition between every forward pair p < q, an a-loop at 0, and a b-loop at n - 1.

Statement

def binary_extremizer_nfa (n : ℕ) : NFA (Fin 2) (Fin n)
Related work
arXiv:2610.08525, Stronger bounds on the degree of ambiguity of finite automata
Verified
29 Oct 2026
Axioms
none listed
Used by 2
  • binary_extremizer_has_singleton_sccsFor every natural number n, the binary extremizer NFA binary_extremizer_nfa n has singleton strongly connected components.
  • binary_extremizer_is_trimFor every positive natural number n, the binary extremizer NFA binary_extremizer_nfa n is trim: every state is reachable from the start…

Read back from the Lean

Definition of binary_extremizer_nfa (n : ℕ), a nondeterministic finite automaton (NFA (Fin 2) (Fin n)) over the two-letter alphabet Fin 2 with states Fin n: - The transition function step p k maps a state p : Fin n and an input symbol k : Fin 2 to the set of states q : Fin n such that at least one of the following holds: 1. p.val < q.val (independent of the input symbol k), 2. k.val = 0 ∧ p.val = 0 ∧ q.val = 0 (a self-loop at state 0 on symbol 0), or 3. k.val = 1 ∧ p.val + 1 = n ∧ q.val = p.val (a self-loop at state n - 1 on symbol 1). - The start states start are the states p : Fin n such that p.val = 0. - The accept states accept are the states q : Fin n such that q.val + 1 = n.

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 n-state binary NFA with initial state 0, accepting state n-1, all forward transitions on both letters, an a-loop at 0, and a b-loop at n-1. -/
def binary_extremizer_nfa (n : ℕ) : NFA (Fin 2) (Fin n) where
  step p k := {q | p.val < q.val ∨ (k.val = 0 ∧ p.val = 0 ∧ q.val = 0) ∨ (k.val = 1 ∧ p.val + 1 = n ∧ q.val = p.val)}
  start := {p | p.val = 0}
  accept := {q | q.val + 1 = n}
See it in the graphDiscuss this resultChallenge it