nfa_transition_graph
def
The 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 u on some input symbol.
Statement
def nfa_transition_graph {α σ : Type*} (A : NFA α σ) : SimpleGraph σ
- Defined in
- arXiv:2610.11717 Sec. 2
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Used by 4
- is_bipartite_cactus_nfaAn NFA A is a bipartite cactus automaton if its undirected transition graph is a cactus and 2-colorable.
- 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…
- nfa_reaches_avoidingTwo 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…
- min_bipartite_cactus_nfa_states_emptyThe empty language over any alphabet has a bipartite cactus NFA with at most one state.
Read back from the Lean
Given an alphabet type α, a state type σ, and an NFA A : NFA α σ, nfa_transition_graph A defines the simple graph on vertex type σ in which two vertices u, v : σ are adjacent if and only if u ≠ v and there exists some symbol a : α such that either v ∈ A.step u a or u ∈ A.step v a.
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
/-- The undirected transition graph G(A) of an NFA A without loops or multiple edges. -/ def nfa_transition_graph {α σ : Type*} (A : NFA α σ) : SimpleGraph σ := SimpleGraph.fromRel (fun u v => ∃ a : α, v ∈ A.step u a)