AFTD Auto-Formalizing Theoretical Domains

nfa_is_finitely_ambiguous

def

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