nfa_is_finitely_ambiguous
An 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 on w is at most N.
Statement
def nfa_is_finitely_ambiguous {α σ : Type*} (M : NFA α σ) : Prop
- Defined in
- arXiv:2610.08525 Sec. 2
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 4
- 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.
- le_nfa_max_ambiguityFor 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…
- 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…
Read back from the Lean
For an NFA M over alphabet α with state type σ, nfa_is_finitely_ambiguous M asserts that there exists a natural number N such that for every word w : List α, the number of accepting runs of M on w (measured by Set.encard) is at most N.
An accepting run is defined as a sequence of states r : Fin (w.length + 1) → σ such that:
1. The start state r 0 is in M.start.
2. The end state r (Fin.last w.length) is in M.accept.
3. For every step index i : Fin w.length, r (i + 1) ∈ M.step (r i) (w.get i).
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
/-- An NFA is finitely ambiguous if the number of accepting runs on any word is uniformly bounded. -/ def nfa_is_finitely_ambiguous {α σ : Type*} (M : NFA α σ) : Prop := ∃ (N : ℕ), ∀ (w : List α), Set.encard { r : Fin (w.length + 1) → σ | r 0 ∈ M.start ∧ r (Fin.last w.length) ∈ M.accept ∧ ∀ (i : Fin w.length), r i.succ ∈ M.step (r i.castSucc) (w.get i) } ≤ N