AFTD Auto-Formalizing Theoretical Domains

le_nfa_max_ambiguity

theoremverified

For any natural numbers n and k and any trim finitely ambiguous NFA M with n states over alphabet Fin k, the degree of ambiguity of M is at most the maximum ambiguity M(n).

Statement

theorem le_nfa_max_ambiguity (n k : ℕ) (M : NFA (Fin k) (Fin n))
    (ht : nfa_is_trim M) (hf : nfa_is_finitely_ambiguous M) :
    nfa_degree_of_ambiguity M ≤ nfa_max_ambiguity n
Source
arXiv:2610.08525 Sec. 5
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • nfa_max_ambiguityThe maximum degree of ambiguity M(n) in ℕ∞ over all trim finitely ambiguous nondeterministic finite automata with n states across all…
  • 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).
  • nfa_degree_of_ambiguityThe degree of ambiguity of an NFA M is the supremum in ℕ∞ over all words w of the number of accepting runs of M on w, measured by…
  • nfa_is_finitely_ambiguousAn NFA M is finitely ambiguous if there exists a natural number N such that for every word w, the number of accepting runs Set.encard of M…

Read back from the Lean

For all natural numbers $n$ and $k$, and every NFA $M$ with alphabet $\mathrm{Fin}(k)$ and state set $\mathrm{Fin}(n)$, if $M$ is trim and finitely ambiguous, then the degree of ambiguity of $M$ is at most nfa_max_ambiguity n.

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 theorem states that the degree of ambiguity of any trim, finitely ambiguous NFA M with n states is bounded above by nfa_max_ambiguity n. By definition, nfa_max_ambiguity n is the supremum of degrees of ambiguity over all alphabet sizes, NFAs with n states, and proofs that the automaton is trim and finitely ambiguous. The bound follows directly by observing that M, together with its alphabet size k and the given hypotheses that it is trim and finitely ambiguous, is one of the members of the family defining the supremum.

  1. It suffices to show that the degree of ambiguity of M is bounded by the iterated supremum defining nfa_max_ambiguity n.

    Unfolding the definition of nfa_max_ambiguity n rewrites the right-hand side of the inequality as the iterated supremum over alphabet sizes k', NFAs M' with state space Fin n, and certificates that M' is trim and finitely ambiguous.

    line 5

      unfold nfa_max_ambiguity
  2. The degree of ambiguity of M is bounded by this supremum.

    Because M has alphabet Fin k and satisfies the trimness hypothesis ht and the finite ambiguity hypothesis hf, it provides valid index witnesses for each level of the supremum. Applying le_iSup_of_le four times instantiates these indices with k, M, ht, and hf, reducing the goal to nfa_degree_of_ambiguity M ≤ nfa_degree_of_ambiguity M, which holds by reflexivity (le_rfl).

    line 6

    uses le_iSup_of_le, le_rfl

      exact le_iSup_of_le k (le_iSup_of_le M (le_iSup_of_le ht (le_iSup_of_le hf le_rfl)))
le_iSup_of_le
In a complete lattice, an element a is bounded above by the supremum ⨆ i, f i whenever a ≤ f j for some index j.
le_rfl
The preorder relation ≤ is reflexive: a ≤ a for every element a.

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 degree of ambiguity of any trim finitely ambiguous NFA is bounded above by nfa_max_ambiguity. -/theorem le_nfa_max_ambiguity (n k : ℕ) (M : NFA (Fin k) (Fin n))    (ht : nfa_is_trim M) (hf : nfa_is_finitely_ambiguous M) :    nfa_degree_of_ambiguity M ≤ nfa_max_ambiguity n := by  unfold nfa_max_ambiguity  exact le_iSup_of_le k (le_iSup_of_le M (le_iSup_of_le ht (le_iSup_of_le hf le_rfl)))
See it in the graphDiscuss this resultChallenge it