Deterministic finite-state automata

Deterministic finite-state automata (DFA) (Hopcroft and Ullman (1979, 16),Salomaa (1973, 26)) may be seen as a special case of Moore machines. A DFA is a five-tuple

$$M=(Q,\Sigma,\delta,q_I,F)$$ (3.3)

where $Q$, $\Sigma$, $\delta$ and $q_I$ have the same meaning as in Mealy and Moore machines and $F\subseteq Q$ is the set of accepting states. If the state reached by the DFA after reading a complete string in $\Sigma^*$ (the set of all finite-length strings over $\Sigma$, including the empty string $\epsilon$) is in $F$ then, the string is accepted; if not, the string is not accepted (or rejected). This would be equivalent to having a Moore machine whose output alphabet has only two symbols, Y (yes) and N (no), and looking only at the last output symbol (not at the whole output string) to decide whether the string is accepted or rejected.

As an example, let $M=(Q,\Sigma,\delta,q_I,F)$ be a DFA such that:

$Q=\{q_1,q_2\}$, $F=\{q_1\}$, $q_I=q_1$.

$\Sigma=\{{\tt0}, {\tt 1}\}$

$\delta(q_1,0)=q_1$
$\delta(q_1,1)=q_2$
$\delta(q_2,0)=q_2$
$\delta(q_2,1)=q_1$

This automaton, which may also be represented as in figure 2.3, accepts only those strings of 0s and 1s having an even number of 1s. Another example of DFA is given by the following definition

$Q=\{q_1,q_2,q_3,q_4\}$, $F=\{q_1,q_2,q_3\}$, $q_I=q_1$.

$\Sigma=\{{\tt0}, {\tt 1}\}$

$\delta(q_1,0)=q_2$, $\delta(q_1,1)=q_1$
$\delta(q_2,0)=q_3$, $\delta(q_2,1)=q_1$
$\delta(q_3,0)=q_4$, $\delta(q_3,1)=q_1$
$\delta(q_4,0)=q_4$, $\delta(q_4,1)=q_4$.

This automaton, which may also be represented as in figure 2.4, accepts only those strings of 0s and 1s not including the substring 000.

Figure 2.3: A deterministic finite-state automaton that accepts only binary strings having an even number of 1s.

Figure 2.4: A deterministic finite-state automaton that accepts only binary strings not containing the sequence ``000''.