nfa_degree_of_ambiguity
The 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 Set.encard.
Statement
noncomputable def nfa_degree_of_ambiguity {α σ : Type*} (M : NFA α σ) : ℕ∞
- Defined in
- arXiv:2610.08525 Sec. 1
- 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 types α and σ and a nondeterministic finite automaton M : NFA α σ, nfa_degree_of_ambiguity M is defined as the supremum in ℕ∞ (extended natural numbers) over all words w : List α of the extended cardinality (Set.encard) of the set of accepting runs of M on w.
An accepting run for a word w is a function r : Fin (w.length + 1) → σ satisfying:
1. r 0 ∈ M.start (the initial state is a start state),
2. r (Fin.last w.length) ∈ M.accept (the final state is an accepting state), and
3. ∀ (i : Fin w.length), r i.succ ∈ M.step (r i.castSucc) (w.get i) (at each step i, the state r (i + 1) is in the set of states reachable from r i on symbol w[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
/-- The degree of ambiguity of an NFA is the supremum in ℕ∞ over all words of its number of accepting runs. -/ noncomputable def nfa_degree_of_ambiguity {α σ : Type*} (M : NFA α σ) : ℕ∞ := ⨆ (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) }