AFTD Auto-Formalizing Theoretical Domains

nfa_is_trim

def

An 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).

Statement

def nfa_is_trim {α σ : Type*} (M : NFA α σ) : Prop
Defined in
arXiv:2610.08525 Sec. 2
Verified
18 Oct 2026
Axioms
none listed
Used by 6
  • 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…
  • binary_extremizer_is_trimFor every positive natural number n, the binary extremizer NFA binary_extremizer_nfa n is trim: every state is reachable from the start…
  • pell_nfa_is_trimThe n-state Pell NFA pell_nfa n is trim: every state is reachable from the start state and can reach an accept state.

Read back from the Lean

Given types α and σ and a nondeterministic finite automaton M : NFA α σ, nfa_is_trim M is defined as the proposition that for every state q : σ: 1. There exists a word w : List α such that q ∈ M.evalFrom M.start w (that is, q is reachable from the set of start states M.start via w), and 2. There exist a word w : List α and a state t : σ such that t ∈ M.accept and t ∈ M.evalFrom {q} w (that is, an accepting state t is reachable from the state q via w).

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 trim if every state is reachable from the start states and co-reachable to an accept state. -/
def nfa_is_trim {α σ : Type*} (M : NFA α σ) : Prop :=
  ∀ (q : σ), (∃ (w : List α), q ∈ M.evalFrom M.start w) ∧
             (∃ (w : List α) (t : σ), t ∈ M.accept ∧ t ∈ M.evalFrom {q} w)
See it in the graphDiscuss this resultChallenge it