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
- binary_extremizer_has_singleton_sccsFor every natural number n, the binary extremizer NFA binary_extremizer_nfa n has singleton strongly connected components.
- pell_nfa_has_singleton_sccsFor every natural number n, the n-state Pell NFA pell_nfa n has singleton strongly connected components.
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