binary_extremizer_nfa
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}