le_nfa_max_ambiguity
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.
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.
unfold nfa_max_ambiguityThe 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).
uses
le_iSup_of_le,le_rflexact 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
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 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)))