AFTD Auto-Formalizing Theoretical Domains

has_strongly_cactus_nfa

def

A 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 accepts exactly L and A is strongly cactus of parity p with initial state s.

Statement

def has_strongly_cactus_nfa {α : Type*} (L : Language α) (p : ZMod 2) : Prop
Source
step towards regular_language_has_bipartite_cactus_nfa
Verified
24 Oct 2026
Axioms
none listed
Built on 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

/-- A language is representable by a finite-state strongly cactus automaton of parity `p` with a distinguished initial state. This is the induction invariant of the paper's Theorem 3.8. -/
def has_strongly_cactus_nfa {α : Type*} (L : Language α) (p : ZMod 2) : Prop := (∃ (σ : Type) (_ : Fintype σ) (A : NFA α σ) (s : σ), A.accepts = L ∧ strongly_cactus_nfa A s p)
See it in the graphDiscuss this resultChallenge it