AFTD Auto-Formalizing Theoretical Domains

nfa_degree_of_ambiguity

def

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