AFTD Auto-Formalizing Theoretical Domains

nfa_max_ambiguity_one_le

theoremverified

The maximum degree of ambiguity M(1) of trim finitely ambiguous nondeterministic finite automata with 1 state is at most 1.

Statement

theorem nfa_max_ambiguity_one_le : nfa_max_ambiguity 1 ≤ 1
Source
arXiv:2610.08525 Sec. 2
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • 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_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_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…

Read back from the Lean

The maximum degree of ambiguity nfa_max_ambiguity 1 (the supremum over all alphabet sizes k : ℕ and all NFAs with alphabet Fin k and state space Fin 1 that are trim and finitely ambiguous, of the degree of ambiguity of the NFA) is less than or equal to 1 (in ℕ∞).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By definition, the maximum ambiguity M(1) is the supremum of the degrees of ambiguity over all trim, finitely ambiguous 1-state NFAs. Using the universal property of the supremum, the inequality reduces to showing that every such individual automaton has degree of ambiguity at most 1. This holds directly by the known lemma that trim, finitely ambiguous 1-state NFAs are unambiguous.

  1. It suffices to show that any trim, finitely ambiguous 1-state NFA has degree of ambiguity at most 1.

    By definition, `nfa_max_ambiguity 1` is the supremum of the degrees of ambiguity over all alphabet sizes k and all 1-state NFAs M that are trim and finitely ambiguous. Unfolding this definition and repeatedly applying `iSup_le` reduces the upper bound to proving that an arbitrary 1-state NFA M over alphabet Fin k has degree of ambiguity at most 1, assuming it is trim (ht) and finitely ambiguous (hf).

    lines 3–11

    uses iSup_le

      unfold nfa_max_ambiguity
      apply iSup_le
      intro k
      apply iSup_le
      intro M
      apply iSup_le
      intro ht
      apply iSup_le
      intro hf
  2. The degree of ambiguity of M is at most 1.

    This is established directly by applying `finitely_ambiguous_nfa_single_state_unambiguous` to the alphabet size k, the automaton M, and the hypotheses ht and hf.

    line 12

    uses finitely_ambiguous_nfa_single_state_unambiguous

      exact finitely_ambiguous_nfa_single_state_unambiguous k M ht hf
iSup_le
A supremum ⨆ i, f i is less than or equal to a if f i ≤ a for all i.
finitely_ambiguous_nfa_single_state_unambiguous
Any trim, finitely ambiguous NFA with a single state has degree of ambiguity at most 1.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The maximum degree of ambiguity of 1-state trim finitely ambiguous NFAs is at most 1. -/theorem nfa_max_ambiguity_one_le : nfa_max_ambiguity 1 ≤ 1 := by  unfold nfa_max_ambiguity  apply iSup_le  intro k  apply iSup_le  intro M  apply iSup_le  intro ht  apply iSup_le  intro hf  exact finitely_ambiguous_nfa_single_state_unambiguous k M ht hf
See it in the graphDiscuss this resultChallenge it