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