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)