nfa_max_ambiguity
The maximum degree of ambiguity M(n) in ℕ∞ over all trim finitely ambiguous nondeterministic finite automata with n states across all finite alphabets.
Statement
noncomputable def nfa_max_ambiguity (n : ℕ) : ℕ∞
- Defined in
- arXiv:2610.08525 Sec. 5
- Verified
- 19 Oct 2026
- Axioms
- none listed
- 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 2
- 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…
Read back from the Lean
nfa_max_ambiguity is a definition that takes a natural number n : ℕ (the number of states) and returns an extended natural number in ℕ∞ (i.e., WithTop ℕ). It is defined as the supremum (least upper bound in ℕ∞) over all:
1. alphabet sizes k : ℕ,
2. nondeterministic finite automata M : NFA (Fin k) (Fin n) with alphabet Fin k and state set Fin n,
3. proofs that M is trim (nfa_is_trim M), and
4. proofs that M is finitely ambiguous (nfa_is_finitely_ambiguous M),
of the degree of ambiguity of M (nfa_degree_of_ambiguity M).
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
/-- Maximum degree of ambiguity M(n) over all trim finitely ambiguous NFAs with n states. -/ noncomputable def nfa_max_ambiguity (n : ℕ) : ℕ∞ := ⨆ (k : ℕ) (M : NFA (Fin k) (Fin n)) (_ : nfa_is_trim M) (_ : nfa_is_finitely_ambiguous M), nfa_degree_of_ambiguity M