Symbol Count by Finite State Machine
Theorem
Let $\Sigma$ be a finite set.
Let $\Pi \subseteq \Sigma$.
For a finite sequence $w = \sequence {a_1, a_2, \dotsc, a_n}$ of elements of $\Sigma$:
- Let $\map c w = \size {\set {i : a_i \in \Pi} }$
Let $k \in \N$.
Then, for each of the following, there exists a finite state machine whose accepted languages is all $w \in \Sigma^*$ such that the condition holds:
- $\map c w < k$
- $\map c w \le k$
- $\map c w > k$
- $\map c w \ge k$
- $\map c w = k$
- $\map c w \ne k$
Proof
$\map c w < k$
Define $F = \tuple {S, A, I, \Sigma, T}$ where:
- $S = \set {s_0, s_1, \dotsc, s_k}$
- $A = \set {s_0, s_1, \dotsc, s_{k - 1} }$
- $I = s_0$
- $\map T {s_i, \sigma} = \begin{cases}
s_{i + 1} & : \sigma \in \Pi \land i < k \\ s_i & : \text {otherwise} \end{cases}$
The machine being in the state $s_i$ indicates that $i$ symbols in $\Pi$ have been read so far, up to a maximum of $k$.
So long as the word ends before the $k$-th symbol in $\Pi$ is read, the machine accepts.
If a $k$-th symbol is read, it is no longer possible for the machine to transition out of $s_k$, and the machine rejects.
$\Box$
$\map c w \le k$
This is equivalent to $\map c w < k + 1$, which has already been shown to exist.
$\Box$
$\map c w > k$
This is equivalent to $\neg \paren {\map c w \le k}$, which exists by Negation of Finite State Machine in addition to the above.
$\Box$
$\map c w \ge k$
This is equivalent to $\neg \paren {\map c w < k}$, which exists by Negation of Finite State Machine in addition to the above.
$\Box$
$\map c w = k$
This is equivalent to $\map c w \le k \land \map c w \ge k$, which exists by Conjunction of Finite State Machines in addition to the above.
$\Box$
$\map c w \ne k$
This is equivalent to $\map c w < k \lor \map c w > k$, which exists by Disjunction of Finite State Machines in addition to the above.
$\blacksquare$