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)