two_way_dfa_mixed_count_le
The number of mixed states is at most the number of states.
Statement
theorem two_way_dfa_mixed_count_le {σ Q : Type*} [Finite Q] (A : two_way_dfa σ Q) : two_way_dfa_mixed_count A ≤ Nat.card Q
- Source
- helper for arXiv:2610.18897 Corollary 7.2 (the bound 4n)
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- two_way_dfaA two-way deterministic finite automaton over the alphabet σ with state set Q: a partial transition δ(q, a) ∈ Q × {left (false), right…
- two_way_dfa_mixed_countb: the number of states that are targets of both a left-moving and a right-moving transition, endmarker transitions included, once the row…
The proof, explained
The number of mixed states of a two-way DFA is defined as the cardinality of a subset of its state type $Q$. Because $Q$ is finite, the cardinality of any of its subsets cannot exceed the total number of states in $Q$. The theorem follows directly by applying the standard lemma that bounds the size of a subset by the cardinality of the ambient type.
The number of mixed states of $A$ is at most the total number of states $|Q|$.
By definition, `two_way_dfa_mixed_count A` is the cardinality (`Set.ncard`) of a subset of states in $Q$ (the mixed states). Applying `Set.ncard_le_card` directly bounds the cardinality of this subset by the cardinality of the ambient finite type $Q$ (`Nat.card Q`).
uses
Set.ncard_le_cardSet.ncard_le_card _
Set.ncard_le_card- For any subset $s$ of a finite type $\alpha$, the cardinality of $s$ is at most the cardinality of $\alpha$ ($|s| \le |\alpha|$).
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem two_way_dfa_mixed_count_le {σ Q : Type*} [Finite Q] (A : two_way_dfa σ Q) : two_way_dfa_mixed_count A ≤ Nat.card Q := Set.ncard_le_card _