AFTD Auto-Formalizing Theoretical Domains

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)
See it in the graphDiscuss this resultChallenge it