AFTD Auto-Formalizing Theoretical Domains

finitely_ambiguous_nfa_single_state_unambiguous

theoremverifiedformalization

For 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 at most 1.

Statement

theorem finitely_ambiguous_nfa_single_state_unambiguous
    (k : ℕ) (M : NFA (Fin k) (Fin 1)) (ht : nfa_is_trim M) (hf : nfa_is_finitely_ambiguous M) :
    nfa_degree_of_ambiguity M ≤ 1
Formalizes
arXiv:2610.08525 Claim 2
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
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 1
  • 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.

Read back from the Lean

For any natural number k and any nondeterministic finite automaton M with alphabet Fin k and state space Fin 1 (a single state): if M is trim (the single state is both reachable from M.start and can reach an accepting state in M.accept), and M is finitely ambiguous (there exists some N : ℕ bounding the number of accepting runs on any word), then the degree of ambiguity of M is at most 1 (the supremum over all words of the number of accepting runs is at most 1).

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

The degree of ambiguity of an NFA is the supremum over all words w of the number of accepting runs on w. To show this is at most 1, it suffices to show that each word has at most one accepting run. Since the state space is Fin 1, there is only one function from the sequence of word positions to states, so any two runs are identical.

  1. It suffices to show that for every word w, the set of accepting runs of M on w has cardinality at most 1.

    Lines 5 and 6 assign the hypotheses `ht` (trimness) and `hf` (finite ambiguity) to dummy variables, leaving them unused. Unfolding `nfa_degree_of_ambiguity` reveals it as the supremum over all words of the cardinality of their accepting runs. By `iSup_le`, showing this supremum is at most 1 reduces to showing that for an arbitrary word w, the number of accepting runs is at most 1.

    lines 5–9

    uses iSup_le

      have _ := ht
      have _ := hf
      unfold nfa_degree_of_ambiguity
      apply iSup_le
      intro w
  2. It suffices to show that the set of accepting runs on w contains at most one element.

    By `Set.encard_le_one_iff_subsingleton`, a set has extended cardinality at most 1 if and only if it is a subsingleton—meaning that any two elements belonging to the set must be equal.

    line 10

    uses Set.encard_le_one_iff_subsingleton

      rw [Set.encard_le_one_iff_subsingleton]
  3. Any two accepting runs on w are equal.

    Let x and y be two accepting runs for w. Each run is a sequence of states, formalised as a function from `Fin (w.length + 1)` into the state space `Fin 1`. Because `Fin 1` has only a single element, the function type `Fin (w.length + 1) → Fin 1` is a subsingleton, so x and y are equal by `Subsingleton.elim`.

    lines 11–12

    uses Subsingleton.elim

      intro x _ y _
      exact Subsingleton.elim x y
iSup_le
The supremum of an indexed family is at most a if every element of the family is at most a.
Set.encard_le_one_iff_subsingleton
A set has extended cardinality at most 1 if and only if it is a subsingleton (any two of its elements are equal).
Subsingleton.elim
In a subsingleton type, any two terms are equal.

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

/-- Every trim finitely ambiguous NFA with 1 state has degree of ambiguity at most 1. -/theorem finitely_ambiguous_nfa_single_state_unambiguous    (k : ℕ) (M : NFA (Fin k) (Fin 1)) (ht : nfa_is_trim M) (hf : nfa_is_finitely_ambiguous M) :    nfa_degree_of_ambiguity M ≤ 1 := by  have _ := ht  have _ := hf  unfold nfa_degree_of_ambiguity  apply iSup_le  intro w  rw [Set.encard_le_one_iff_subsingleton]  intro x _ y _  exact Subsingleton.elim x y
See it in the graphDiscuss this resultChallenge it