AFTD Auto-Formalizing Theoretical Domains

nfa_has_singleton_sccs

deforiginal

An NFA M has singleton strongly connected components if for all states p and q, whenever q is reachable from {p} by some word and p is reachable from {q} by some word, p = q.

Statement

def nfa_has_singleton_sccs {α σ : Type*} (M : NFA α σ) : Prop
Related work
arXiv:2610.08525 Section 2
Verified
24 Oct 2026
Axioms
none listed
Used by 2

Read back from the Lean

For an NFA M with alphabet α and state type σ, nfa_has_singleton_sccs M asserts that for all states p, q : σ, if there exists a word w₁ : List α such that q ∈ M.evalFrom {p} w₁ (i.e., q is reachable from p), and there exists a word w₂ : List α such that p ∈ M.evalFrom {q} w₂ (i.e., p is reachable from q), then p = q. In other words, mutual reachability in the state transition graph of M is antisymmetric (no two distinct states can reach each other).

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 has singleton strongly connected components if mutual reachability between states is antisymmetric. -/
def nfa_has_singleton_sccs {α σ : Type*} (M : NFA α σ) : Prop := ∀ p q : σ, (∃ w₁, q ∈ M.evalFrom {p} w₁) → (∃ w₂, p ∈ M.evalFrom {q} w₂) → p = q
See it in the graphDiscuss this resultChallenge it