AFTD Auto-Formalizing Theoretical Domains

strongly_cactus_nfa

def

An 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 transition graph is a cactus with a transition-compatible colouring that gives s colour 0 and every accepting state colour p; every component of G(A) - s has at most one entry state and contains an accepting state; and every state that is the source of a transition into an accepting state is joined to s by a unique path.

Statement

def strongly_cactus_nfa {α σ : Type*} (A : NFA α σ) (s : σ) (p : ZMod 2) : Prop
Source
step towards regular_language_has_bipartite_cactus_nfa
Verified
24 Oct 2026
Axioms
none listed
Built on 3
  • 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…
  • simple_graph_is_cactusA simple graph is a cactus if any two simple cycles that share an edge have identical edge sets (every edge belongs to at most one simple…
  • 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
  • has_strongly_cactus_nfaA language L has a strongly cactus NFA of parity p when there are a finite state type σ, an NFA A over σ, and a state s such that A…

Lean source view module on GitHub

/-- The paper's "strongly cactus automaton of parity p" (Definition 3.2): the initial state is the single start state and no transition enters it, the transition graph is a cactus and 2-coloured by a transition-compatible `χ` with `χ s = 0` and `χ f = p` for accepting `f`, every component of `G(A) - s` (read as: all states other than `s`, grouped by `nfa_reaches_avoiding`) has at most one entry state and contains an accepting state, and every possible source of a last transition off the initial state is joined to `s` by a unique path.

This is the invariant that the paper's Section 3 constructions preserve; it is what makes the Kleene-star construction work. -/
def strongly_cactus_nfa {α σ : Type*} (A : NFA α σ) (s : σ) (p : ZMod 2) : Prop := A.start = {s} ∧
  simple_graph_is_cactus (nfa_transition_graph A) ∧
  (∀ (q : σ) (a : α), s ∉ A.step q a) ∧
  (∀ q : σ, Nonempty ((nfa_transition_graph A).Walk s q)) ∧
  (∃ χ : σ → ZMod 2, χ s = 0 ∧
    (∀ (q : σ) (a : α) (r : σ), r ∈ A.step q a → χ r = χ q + 1) ∧
    (∀ f : σ, f ∈ A.accept → χ f = p)) ∧
  (∀ (t₁ t₂ : σ), t₁ ≠ s → t₂ ≠ s → (∃ a : α, t₁ ∈ A.step s a) → (∃ a : α, t₂ ∈ A.step s a) →
    (∃ u : σ, nfa_reaches_avoiding A s t₁ u ∧ nfa_reaches_avoiding A s t₂ u) → t₁ = t₂) ∧
  (∀ u : σ, u ≠ s → ∃ f : σ, f ∈ A.accept ∧ nfa_reaches_avoiding A s u f) ∧
  (∀ g : σ, g ≠ s → (∃ (a : α) (f : σ), f ∈ A.accept ∧ f ∈ A.step g a) →
    ∀ (w₁ w₂ : (nfa_transition_graph A).Walk s g), w₁.IsPath → w₂.IsPath → w₁.support = w₂.support)
See it in the graphDiscuss this resultChallenge it