nfa_max_ambiguity_one_le
The maximum degree of ambiguity M(1) of trim finitely ambiguous nondeterministic finite automata with 1 state is at most 1.
Statement
theorem nfa_max_ambiguity_one_le : nfa_max_ambiguity 1 ≤ 1- Source
- arXiv:2610.08525 Sec. 2
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- nfa_max_ambiguityThe maximum degree of ambiguity M(n) in ℕ∞ over all trim finitely ambiguous nondeterministic finite automata with n states across all…
- finitely_ambiguous_nfa_single_state_unambiguousFor every natural number k and every trim finitely ambiguous NFA M with alphabet Fin k and 1 state, the degree of ambiguity of M in ℕ∞ is…
- 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…
- 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…
Read back from the Lean
The maximum degree of ambiguity nfa_max_ambiguity 1 (the supremum over all alphabet sizes k : ℕ and all NFAs with alphabet Fin k and state space Fin 1 that are trim and finitely ambiguous, of the degree of ambiguity of the NFA) is less than or equal to 1 (in ℕ∞).
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
By definition, the maximum ambiguity M(1) is the supremum of the degrees of ambiguity over all trim, finitely ambiguous 1-state NFAs. Using the universal property of the supremum, the inequality reduces to showing that every such individual automaton has degree of ambiguity at most 1. This holds directly by the known lemma that trim, finitely ambiguous 1-state NFAs are unambiguous.
It suffices to show that any trim, finitely ambiguous 1-state NFA has degree of ambiguity at most 1.
By definition, `nfa_max_ambiguity 1` is the supremum of the degrees of ambiguity over all alphabet sizes k and all 1-state NFAs M that are trim and finitely ambiguous. Unfolding this definition and repeatedly applying `iSup_le` reduces the upper bound to proving that an arbitrary 1-state NFA M over alphabet Fin k has degree of ambiguity at most 1, assuming it is trim (ht) and finitely ambiguous (hf).
uses
iSup_leunfold nfa_max_ambiguity apply iSup_le intro k apply iSup_le intro M apply iSup_le intro ht apply iSup_le intro hf
The degree of ambiguity of M is at most 1.
This is established directly by applying `finitely_ambiguous_nfa_single_state_unambiguous` to the alphabet size k, the automaton M, and the hypotheses ht and hf.
uses
finitely_ambiguous_nfa_single_state_unambiguousexact finitely_ambiguous_nfa_single_state_unambiguous k M ht hf
iSup_le- A supremum ⨆ i, f i is less than or equal to a if f i ≤ a for all i.
finitely_ambiguous_nfa_single_state_unambiguous- Any trim, finitely ambiguous NFA with a single state has degree of ambiguity at most 1.
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 maximum degree of ambiguity of 1-state trim finitely ambiguous NFAs is at most 1. -/theorem nfa_max_ambiguity_one_le : nfa_max_ambiguity 1 ≤ 1 := by unfold nfa_max_ambiguity apply iSup_le intro k apply iSup_le intro M apply iSup_le intro ht apply iSup_le intro hf exact finitely_ambiguous_nfa_single_state_unambiguous k M ht hf