nfa_complies_ida
def
An NFA complies with IDA if there exist distinct states p and q and a word v such that p is reachable from p by v, q is reachable from p by v, and q is reachable from q by v.
Statement
def nfa_complies_ida {α σ : Type*} (M : NFA α σ) : Prop
- Source
- step towards finitely_ambiguous_nfa_pell_lower_bound
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Used by 1
- pell_nfa_no_idaThe Pell automaton A_n does not comply with IDA: there are no distinct states p, q and no word v such that p is reachable from p by v, q…
Lean source view module on GitHub
/-- The IDA property of Weber and Seidl: p -v→ p -v→ q -v→ q for a single word v, read here as reachability by one word. -/ def nfa_complies_ida {α σ : Type*} (M : NFA α σ) : Prop := ∃ p q : σ, p ≠ q ∧ ∃ v : List α, p ∈ M.evalFrom {p} v ∧ q ∈ M.evalFrom {p} v ∧ q ∈ M.evalFrom {q} v