two_way_dfa_mixed_count
def
b: the number of states that are targets of both a left-moving and a right-moving transition, endmarker transitions included, once the row (f, L) is deleted.
Statement
noncomputable def two_way_dfa_mixed_count {σ Q : Type*} (A : two_way_dfa σ Q) : ℕ
- Defined in
- arXiv:2610.18897 (A factor-two lower bound for complementing two-way deterministic finite automata), Corollary 7.2: the number b of mixed states
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Built on 1
- two_way_dfaA two-way deterministic finite automaton over the alphabet σ with state set Q: a partial transition δ(q, a) ∈ Q × {left (false), right…
- Used by 1
- two_way_dfa_mixed_count_leThe number of mixed states is at most the number of states.
Lean source view module on GitHub
noncomputable def two_way_dfa_mixed_count {σ Q : Type*} (A : two_way_dfa σ Q) : ℕ := {q : Q | ((∃ p a, A.δ p a = some (q, false)) ∨ ∃ p, A.δR p = some q) ∧ ((∃ p a, A.δ p a = some (q, true)) ∨ ∃ p, p ≠ A.f ∧ A.δL p = some q)}.ncard