finitely_ambiguous_nfa_single_state_unambiguous
For 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 at most 1.
Statement
theorem finitely_ambiguous_nfa_single_state_unambiguous
(k : ℕ) (M : NFA (Fin k) (Fin 1)) (ht : nfa_is_trim M) (hf : nfa_is_finitely_ambiguous M) :
nfa_degree_of_ambiguity M ≤ 1- Formalizes
- arXiv:2610.08525 Claim 2
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_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_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…
- Used by 1
- nfa_max_ambiguity_one_leThe maximum degree of ambiguity M(1) of trim finitely ambiguous nondeterministic finite automata with 1 state is at most 1.
Read back from the Lean
For any natural number k and any nondeterministic finite automaton M with alphabet Fin k and state space Fin 1 (a single state): if M is trim (the single state is both reachable from M.start and can reach an accepting state in M.accept), and M is finitely ambiguous (there exists some N : ℕ bounding the number of accepting runs on any word), then the degree of ambiguity of M is at most 1 (the supremum over all words of the number of accepting runs is at most 1).
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 degree of ambiguity of an NFA is the supremum over all words w of the number of accepting runs on w. To show this is at most 1, it suffices to show that each word has at most one accepting run. Since the state space is Fin 1, there is only one function from the sequence of word positions to states, so any two runs are identical.
It suffices to show that for every word w, the set of accepting runs of M on w has cardinality at most 1.
Lines 5 and 6 assign the hypotheses `ht` (trimness) and `hf` (finite ambiguity) to dummy variables, leaving them unused. Unfolding `nfa_degree_of_ambiguity` reveals it as the supremum over all words of the cardinality of their accepting runs. By `iSup_le`, showing this supremum is at most 1 reduces to showing that for an arbitrary word w, the number of accepting runs is at most 1.
uses
iSup_lehave _ := ht have _ := hf unfold nfa_degree_of_ambiguity apply iSup_le intro w
It suffices to show that the set of accepting runs on w contains at most one element.
By `Set.encard_le_one_iff_subsingleton`, a set has extended cardinality at most 1 if and only if it is a subsingleton—meaning that any two elements belonging to the set must be equal.
uses
Set.encard_le_one_iff_subsingletonrw [Set.encard_le_one_iff_subsingleton]Any two accepting runs on w are equal.
Let x and y be two accepting runs for w. Each run is a sequence of states, formalised as a function from `Fin (w.length + 1)` into the state space `Fin 1`. Because `Fin 1` has only a single element, the function type `Fin (w.length + 1) → Fin 1` is a subsingleton, so x and y are equal by `Subsingleton.elim`.
uses
Subsingleton.elimintro x _ y _ exact Subsingleton.elim x y
iSup_le- The supremum of an indexed family is at most a if every element of the family is at most a.
Set.encard_le_one_iff_subsingleton- A set has extended cardinality at most 1 if and only if it is a subsingleton (any two of its elements are equal).
Subsingleton.elim- In a subsingleton type, any two terms are equal.
- The hypotheses `ht` (that M is trim) and `hf` (that M is finitely ambiguous), referenced on lines 5–6, are not actually used in the proof. The theorem holds for every NFA with a single state purely because there is at most one run of any given length.
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.
/-- Every trim finitely ambiguous NFA with 1 state has degree of ambiguity at most 1. -/theorem finitely_ambiguous_nfa_single_state_unambiguous (k : ℕ) (M : NFA (Fin k) (Fin 1)) (ht : nfa_is_trim M) (hf : nfa_is_finitely_ambiguous M) : nfa_degree_of_ambiguity M ≤ 1 := by have _ := ht have _ := hf unfold nfa_degree_of_ambiguity apply iSup_le intro w rw [Set.encard_le_one_iff_subsingleton] intro x _ y _ exact Subsingleton.elim x y