What is a DFA?

A deterministic finite automaton (DFA) $A=(Q,\Sigma,\delta,q_0,F)$ is given by:

1. A finite set of states $Q$,

2. A finite set of input symbols $\Sigma$,

3. A transition function $\delta \in Q\times\Sigma \to Q$,

4. An initial state $q_0 \in Q$,

5. A set of accepting states $F\subseteq Q$.

As an example consider the following automaton

$$B=(\{ q_0,q_1,q_2 \},\{ 0,1 \},\delta_B,q_0,\{q_2\})$$

where

$$\delta_B = \{ ((q_0,0),q_1),((q_0,1),q_0),((q_1,0),q_1),((q_1,1),q_2), ((q_2,0),q_2),((q_2,1),q_2) \}$$

The DFA may be more conveniently represented by a transition table:

$$\begin{array}{r\vert\vert c\vert c} & 0 & 1 \hline\hlin... ...q_0 \\ q_1 & q_1 & q_2 \\ {*} q_2 & q_2 & q_2 \end{array}$$

The table represents the function $\delta$, i.e. to find the value of $\delta(q,x)$ we have to look at the row labelled $q$ and the column labelled $x$. The initial state is marked by an $\to$ and all final states are marked by ${*}$.

Yet another, optically more inspiring, alternative are transition diagrams:

There is an arrow into the initial state and all final states are marked by double rings. If $\delta(q,x)=q'$ then there is an arrow from state $q$ to $q'$ which is labelled $x$.

We write $\Sigma^*$ for the set of words (i.e. sequences) over the alphabet $\Sigma$. This includes the empty word which is written $\epsilon$. I.e.

$$\{0,1\}^* = \{ \epsilon,0,1,00,01,10,11,000,\dots \}$$