DFA design patterns and counting states

Why it exists

Designing a DFA is the creative half of the subject and the half GATE tests most: give a DFA for this language, or how many states does the minimum DFA for this language have? There is no algorithm for the first (you must see what the machine has to remember), but a handful of patterns cover almost every exam question. This page lists them, with the number of states each needs, and says how to confirm that the number cannot be lowered.

Prerequisites

You need the DFA and its extended transition function (DFA).

Precise definitions

Two strings are distinguishable (with respect to a language $L$) if some continuation $z$ is accepted after one and rejected after the other: $xz \in L$ but $yz \notin L$. In a DFA, distinguishable strings must lead to different states. If $n$ strings are pairwise distinguishable, every DFA for $L$ needs at least $n$ states. Conversely, if every state can be matched to a set of indistinguishable strings, the DFA is minimal. The classes of indistinguishable strings are the Myhill-Nerode classes; their number is the number of states of the minimal complete DFA.

Minimal DFA. A complete DFA with the fewest states among all complete DFAs for the language (it is unique up to renaming; see minimisation).

Product of two DFAs. For DFAs $M_1 = (Q_1, \Sigma, \delta_1, s_1, F_1)$ and $M_2 = (Q_2, \Sigma, \delta_2, s_2, F_2)$ the product has states $Q_1 \times Q_2$, start $(s_1, s_2)$ and $\delta((p, q), a) = (\delta_1(p, a), \delta_2(q, a))$; it runs both machines in parallel. Choosing the accepting pairs as $F_1 \times F_2$ gives the intersection, $(F_1 \times Q_2) \cup (Q_1 \times F_2)$ the union, $F_1 \times (Q_2 \setminus F_2)$ the difference.

How it works

The method

1. Decide what the machine must remember about the part of the string read so far (a number modulo $k$, the last few symbols, which flags have been seen).
2. Give each different memory content one state, and write the transitions by asking "if I remember this and read $a$, what must I remember now?".
3. Mark as accepting the states whose memory content makes the string acceptable.
4. Check short strings including $\varepsilon$, and ask whether two states could be merged (no string distinguishes them).

The patterns and their sizes

The table lists the machines of the patterns below. "States of the DFA built" is the size of the machine written down (complete, only reachable states); "states of the minimal DFA" is what minimisation leaves; here they agree because each machine was designed to remember exactly what is needed.

Counting modulo $k$ (one counter). "The number of $a$s is $\equiv r \pmod k$": $k$ states $c_0, \ldots, c_{k-1}$, the symbol $a$ moves $c_i \to c_{i+1 \bmod k}$, other symbols stay. Length $\equiv r \pmod k$: the same with every symbol counting. Needs exactly $k$ states.

Two counters. For the number of $a$s modulo $k$ and the number of $b$s modulo $m$: the product, $k \cdot m$ states (6 for modulo $2$ and modulo $3$, as in the table). Counters on the same symbol combine to $\operatorname{lcm}(k, m)$ states: "$|w|_a$ even and $|w|_a$ divisible by $3$" is "divisible by $6$", $6$ states, and "divisible by $2$ and by $4$" is "divisible by $4$": $4$ states, not $8$.

Suffix patterns (ends with $w$). The state remembers the longest suffix of the input that is a prefix of $w$: $|w| + 1$ states ($q_0, \ldots, q_{|w|}$). On a mismatch the machine does not return to $q_0$ but to the longest prefix of $w$ that is still a suffix of the new text (the idea of the Knuth-Morris-Pratt algorithm); for $w = 01$ and $q_2$ reading $0$ it goes to $q_1$ (the new $0$ may start another $01$).

Substring patterns (contains $w$). The same machine with an absorbing accepting state at the end: $|w| + 1$ states. (Contains $aba$: $4$.)

Prefix patterns (starts with $w$). The machine must also reject once the beginning is wrong, so it needs a dead state: $|w| + 2$ states. (Starts with $ab$: $4$: start, "read $a$", accepting, dead.)

Length conditions. Exactly $n$ symbols: $n + 2$ states (lengths $0..n$ plus a dead state). At most $n$ symbols: also $n + 2$. At least $n$ symbols: $n + 1$ (no dead state; the last state is absorbing and accepting). Any finite language whose longest string has length $n$ needs at least $n + 2$ states.

Occurrence counts. Exactly $k$ symbols $a$: $k + 2$ states (counts $0..k$ and a dead state). At most $k$ $a$s: $k + 2$ states. At least $k$ $a$s: $k + 1$ states. "At least one $a$ and at least one $b$": $4$ states (neither, only $a$, only $b$, both).

Binary numbers divisible by $k$. Keep the remainder $r$; reading the bit $b$ gives $(2r + b) \bmod k$. This gives $k$ states, and for odd $k$ that is minimal ($k = 3$: $3$; $k = 5$: $5$; $k = 7$: $7$). For even $k = 2^j m$ with $m$ odd, fewer are needed: the minimal DFA has $m + j$ states (for $k = 4$: $3$; $k = 6$: $4$; $k = 8$: $4$; $k = 10$: $6$; confirmed by minimisation for $k$ up to $16$).

Combining machines

• Intersection and union ("$|w|_a$ even and ends with $b$", "...or ..."): product construction. The number of states is at most $|Q_1| \cdot |Q_2|$ and may be smaller after minimisation.
• Complement: swap accepting and non-accepting states of a complete DFA; the number of states stays the same. (A language and its complement need the same number of DFA states, confirmed for nine of the languages above.)
• Difference $L_1 \setminus L_2 = L_1 \cap \overline{L_2}$.

When a DFA is not enough

A DFA has finitely many states, so it cannot remember an unbounded count ($a^n b^n$) or compare two arbitrarily long pieces ($ww$). The languages for which the minimal DFA is much larger than an NFA are those that need to remember a position far back: the $n$-th symbol from the end needs $2^n$ DFA states against $n + 1$ NFA states (subset construction).

An example in detail: contains $aba$

Four states: $s_0$ (no progress), $s_1$ (last symbol is the $a$ that could start $aba$), $s_2$ (have $ab$), $s_3$ (found, accepting, absorbing). From $s_1$ reading $a$ stays in $s_1$ (the new $a$ may start the pattern); from $s_2$ reading $b$ goes to $s_0$ (the text ends in $abb$: no progress), reading $a$ goes to $s_3$. The run on $bbabab$:

Worked examples

Cheat box

Traps and GATE patterns

Connections

The machines here are DFAs (DFA); the question "which states can be merged" is answered by minimisation; the product construction proves that the regular languages are closed under union and intersection (closure properties); languages that need exponentially more states than an NFA are the subject of the subset construction.

PYQs

Let Σ = {1,2,3,4}. For x ∈ Σ* , let prod(x) be the product of
symbols in x modulo 7. We take prod(ε) =1,where ε is the
null string .
For example, prod(124) = (1 × 2 × 4) mod 7 = 1.
Define L = {x ∈ Σ* | prod(x) = 2}.
The number of states in a minimum state DFA for L is
___________. (Answer in integer)

Consider the language L over the alphabet {0, 1}, given
below: L = {w ∈ {0, 1}* | w does not contain three or more
consecutive 1's}. The minimum number of states in a
Deterministic Finite-State Automaton (DFA) for L is _____.

THEORY OF COMPUTATION

Consider the following language.
L = {x ε {a,b}* | number of a's in x is divisible by 2 but
not divisible by 3}. The minimum number of states in a
DFA that accepts L is _______.

Consider the set of strings on {0,1} in which, every
substring of 3 symbols has at most two zeros. For example,
001110 and 011001 are in the language, but 100010 is not.
All strings of length less than 3 are also in the language. A
partially completed DFA that accepts this language is
shown below.

THEORY OF COMPUTATION

The missing arcs in the DFA are:

Given below are two finite state automata (-> indicates
the start state and F indicates a final state)
Automaton Y

a
b
→1
1
2
2(F)
2
1

Automaton Z

a
b
→1
2
2
2(F)
1
1
Which of the following represents the product
automaton Z × Y?

Consider the following DFA in which S0 is the start
state and S1,S3 are the final states.

What language does this DFA recognize?

Self-check

Revision card

References