Automata

An automata $M$ for a Language $A$ scans the input string $w$ from left to right, processing one symbol at each step, and once finished, either rejects or accepts $w$. That is, whether $w$ belongs to $A$ or not.

State

Whenever $M$ reads a symbol, the state of the automata may or may not change. We can classify $M$ into two types of automata based on its number of states: finite or infinite state automata.

Initial and accepting states

If $Q$ is the set of all states of $M$, one of these states has to be the initial state, usually denoted $q_0$. We can then have one or more accepting states. If after finishing string $w$ our automata ends up at an accepting state, then we say that $w$ is accepted and belongs in the Language. Otherwise, $w$ is rejected.

Finite-state automata

If automata $M$ has finite state, it means there is a fixed number of positions that the machine can be at, at all possible times.

We transition to and from states every time a new symbol is processed. This determines the set of all possible next states, or if we move at all.

Deterministic or not?

We can further differentiate automata based on the number of transitions out of a state. If there’s only one, then we can deterministically say what our next state is. This is known as a DFA. Otherwise, it’s a nondeterministic finite automata.

Proving lower bound for number of automata states

Lemma 1

If a DFA $M$ accepts a Language $A$ and strings $u$ and $v$ are distinguishable with respect to $A$, then

$${\delta }^{\ast }(q_0,u)\ne {\delta }^{\ast }(q_0,v)$$

Proof by contradiction. Assume ${\delta }^{\ast }(q_0,u)={\delta }^{\ast }(q_0,v)=q$ and $u$ and $v$ are distinguishable. By definition, there exists a string $w$ such that one of $u.w$ and $v.w$ is in $A$, and the other is not.

However, $\delta (q,w)$ will lead both $u$ and $v$ to the same state. $M$ either accepts or rejects both $u$ and $v$. Therefore we have a contradiction.

Lemma 2

If $S=\{w_1,w_2,\dots ,w_k\}$ is a set of $k$ pairwise, distinguishable strings, then every DFA for $A$ must have at least $k$ states.

This follows from the previous lemma that states that distinguishable strings will end up in different states, therefore there must exist at least $k$ of them.

Example

$\Sigma =\{\text{a, b}\}$ and $A_2=\{w\mid \text{second symbol in }w\text{ equals a}\}$

Consider $\{ϵ\text{, a, ab, aa}\}$. All of these strings are distinguishable with respect to $A_2$. This means that the DFA for this set must have at least four states.

Example

$\Sigma =\{\text{a, b}\}$ and for each number $k$, let $A_k=\{w\mid k\text{th symbol in }w\text{ equals a}\}$

Here, every symbol up to the $k-1$th symbol doesn’t really matter, but we have to transition through them. Then depending on $\text{a}$ or $\text{b}$, we need two more states (one accepting, one rejecting). Therefore we need $k+2$ different states, because $(k-1)+1+2$. we need an extra for $q_0$.

We showed that $k+2$ is sufficient i.e. it’s enough. Now we need to show that $k+2$ is also necessary i.e. we can’t possibly use less states.

Showing necessity (at least $k$)

The general strategy is to convert each of the $k$ states into a possible string that represents the state, and prove that every pair of strings $\in S$ is pairwise distinguishable. We may need to case on the strings in $S$ because they have different properties.

Example

Consider the set of $k+2$ strings $\{ϵ,b,b^2,\dots ,b^k,a^k\}$. we have to prove that every pair of strings in this set is distinguishable w.r.t. $A_k$.