AFTD Auto-Formalizing Theoretical Domains

nfa_max_ambiguity

def

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
See it in the graphDiscuss this resultChallenge it