AFTD Auto-Formalizing Theoretical Domains

nfa_reaches_avoiding

def

Two states u, v of an NFA A are connected inside the transition graph with the initial state s deleted when some walk from u to v avoids s at every vertex.

Statement

def nfa_reaches_avoiding {α σ : Type*} (A : NFA α σ) (s u v : σ) : Prop
Source
step towards regular_language_has_bipartite_cactus_nfa
Verified
24 Oct 2026
Axioms
none listed
Built on 1
  • nfa_transition_graphThe transition graph of an NFA A has an undirected edge between distinct states u and v if there is a transition from u to v or from v to…
Used by 1
  • strongly_cactus_nfaAn NFA A is a strongly cactus automaton of parity p with initial state s when: s is the only start state and no transition enters s; the…

Lean source view module on GitHub

/-- Walks of the transition graph from `u` to `v` that avoid the distinguished state `s`; this is the formal stand-in for "u and v lie in the same component of G(A) - s". -/
def nfa_reaches_avoiding {α σ : Type*} (A : NFA α σ) (s u v : σ) : Prop := ∃ w : (nfa_transition_graph A).Walk u v, ∀ x ∈ w.support, x ≠ s
See it in the graphDiscuss this resultChallenge it