Finite-state machines and DFAs

The idea

Think of a turnstile. It is either locked or unlocked. A coin unlocks it; a push while unlocked lets you through and locks it again; a push while locked does nothing. Two states and a rule for each (state, input) pair describe it completely. A deterministic finite automaton, or DFA, is that idea made precise, with some states marked as accepting so that the machine can answer yes or no about the input it has read.

Definition

A DFA is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$ where

$Q$ is a finite set of states,
$\Sigma$ is a finite alphabet of input symbols,
$\delta : Q \times \Sigma \to Q$ is the transition function,
$q_0 \in Q$ is the start state, and
$F \subseteq Q$ is the set of accepting states.

The DFA accepts a string if, starting in $q_0$ and following $\delta$ for each symbol in turn, it ends in a state of $F$ . The set of strings it accepts is its language.

“Deterministic” means there is exactly one next state for each state and symbol, so a given input always produces the same run. In diagrams, states are circles, accepting states have a double ring, the start state has an incoming arrow, and each transition is an arrow labelled with its symbol.

Build one and run it

The builder starts with a machine for “binary strings with an even number of 0s”. Edit the transition table, rename states, tick accepting states, or start from another preset. Then type a string and step through the run: the tape shows which symbol is being read and the diagram highlights the transition taken. A transition left as “— (dead)” sends the run to an implicit dead state that rejects whatever follows.

DFA builder and testerEdit the transition table, drag states to tidy the diagram, then run a string through it.

Pseudocode

q ← start state
for each symbol c of the input, left to right:
if δ(q, c) is undefined: reject (fall into the dead state)
q ← δ(q, c)
accept if q is an accepting state, otherwise reject

Result

Run a string to see the verdict.

Checks

Shortest accepted strings

Test many strings

1 / 1

Designing a DFA: decide what to remember

The whole art is choosing the states. Ask: what is the least I need to remember about the input so far to finish the job? Each distinct thing you might need to remember becomes a state.

For “an even number of 0s”, only the parity of the 0s matters: two states.
For “ends in ab”, you need to know how much of ab you have just seen: nothing, a, or ab. Three states.
For “contains 101”, you track the longest prefix of 101 that the input currently ends with, plus a final “seen it” state that loops on everything.

Worked example: binary multiples of 3

Read a binary number from its most significant bit. If the value so far is $v$ , reading bit $b$ makes it $2v + b$ . To decide divisibility by 3 we only need $v \bmod 3$ , which takes 3 values. So the states are the remainders $r_0, r_1, r_2$ , with

\delta(r_i, b) = r_{(2i + b) \bmod 3},

start state $r_0$ and accepting state $r_0$ . On input 110 (six): $r_0 \xrightarrow{1} r_1 \xrightarrow{1} r_0 \xrightarrow{0} r_0$ , accept. On 111 (seven): $r_0 \xrightarrow{1} r_1 \xrightarrow{1} r_0 \xrightarrow{1} r_1$ , reject. Load the “Binary multiple of 3” preset to check.

Regular languages

A language is regular if some DFA accepts it. Regular languages have useful closure properties:

Complement. Swap accepting and non-accepting states (after filling in any missing transitions).
Intersection and union. Run two DFAs side by side. The product construction uses pairs of states $(p, q)$ and moves both components at once; it accepts when both (for intersection) or either (for union) would.
Concatenation and repetition (Kleene star) are also regular, though the construction goes through nondeterministic automata.

An NFA may have several possible next states, or none, and accepts if any run ends in an accepting state. NFAs are often far smaller and easier to design, but Rabin and Scott showed in 1959 that they recognise exactly the same languages: the subset construction builds a DFA whose states are sets of NFA states. The price can be steep, up to $2^n$ DFA states for an $n$ -state NFA.

Kleene’s theorem completes the picture: regular expressions, NFAs and DFAs all describe the same class of languages. This is why a regular-expression engine can compile a pattern into an automaton and match text in a single pass.

What a DFA cannot do

A DFA with $k$ states remembers at most $k$ different things about the past. So it cannot recognise a language that requires unbounded counting. The standard example is

L = \{ 0^n 1^n : n \ge 0 \} = \{\varepsilon, 01, 0011, 000111, \dots\}.

Suppose a DFA with $k$ states accepted $L$ . Feed it $0^0, 0^1, \dots, 0^k$ : that is $k + 1$ strings and only $k$ states, so by the pigeonhole principle two of them, $0^i$ and $0^j$ with $i \ne j$ , leave it in the same state. From then on it cannot tell them apart, so it treats $0^i 1^i$ and $0^j 1^i$ the same way. But the first is in $L$ and the second isn’t. Contradiction: no DFA accepts $L$ .

That argument is a special case of the Myhill–Nerode theorem, which says a language is regular exactly when it has finitely many “distinguishable” classes of prefixes, and that the number of classes is the size of the smallest DFA for it. Balanced parentheses, palindromes and correctly nested HTML are all non-regular for the same reason. Recognising them needs a stack, which leads to pushdown automata and context-free grammars.

Minimisation

Two states are equivalent if no input string can tell them apart: from either one, exactly the same strings lead to acceptance. Merging equivalent states (and removing unreachable ones) gives the unique smallest DFA for the language. The classic algorithm starts by splitting states into accepting and non-accepting, then keeps refining the groups whenever two states in a group go to different groups on some symbol.

Where finite-state machines are used

Lexical analysis. A compiler’s first phase turns characters into tokens (identifiers, numbers, keywords) with a DFA generated from regular expressions.
Protocols. TCP connections move through named states such as LISTEN, SYN-SENT and ESTABLISHED.
User interfaces and games. A form that can be editing, submitting, failed or done is a state machine; writing it as one makes impossible states impossible.
Hardware. Sequential circuits are finite-state machines built from flip-flops and logic gates, designed with Boolean algebra.

References

M. O. Rabin and D. Scott, “Finite automata and their decision problems”, IBM Journal of Research and Development 3(2), 1959. doi:10.1147/rd.32.0114
A. Nerode, “Linear automaton transformations”, Proceedings of the American Mathematical Society 9(4), 1958. doi:10.1090/S0002-9939-1958-0135681-9
M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2012. Chapter 1.
J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006.