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$