AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_mixed_count_le

theoremverified

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.

  1. 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`).

    line 3

    uses Set.ncard_le_card

      Set.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 _
See it in the graphDiscuss this resultChallenge it