Deterministic Finite Automata: short notes (Theory of Computation)

Introduction

A deterministic finite automaton (DFA) is a finite-state machine that reads an input string from left to right, one symbol at a time, and either accepts or rejects. At every step the next state is uniquely determined by the current state and the current symbol. DFAs recognize exactly the regular languages.

The working skills are designing a DFA for a stated language, simulating a given DFA on a string, counting states, and reasoning about what language a transition diagram accepts. This note fixes the formal definition, the extended transition function, design patterns and two fully checked examples: binary integers divisible by 3, and strings ending with 01.

Prerequisites

Alphabets, Strings and Languages: strings, $\Sigma^*$ , languages.

Core concepts

Formal definition

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

$Q$ is a finite nonempty set of states.
$\Sigma$ is the input alphabet.
$\delta: Q \times \Sigma \to Q$ is the transition function (total: defined for every state and symbol).
$q_0 \in Q$ is the start state.
$F \subseteq Q$ is the set of accepting (final) states.

Deterministic and total. From each state, for each symbol, there is exactly one next state. An incomplete diagram is conventionally read as having a missing dead (sink) state that rejects and stays on every symbol; state it when you add one.

How a DFA processes a string

The transition function extends to strings by $\hat{\delta}: Q \times \Sigma^* \to Q$ :

\hat{\delta}(q, \varepsilon) = q, \qquad \hat{\delta}(q, wa) = \delta\bigl(\hat{\delta}(q, w), a\bigr).

The DFA accepts $w$ iff $\hat{\delta}(q_0, w) \in F$ . The language of $M$ is

L(M) = \{ w \in \Sigma^* \mid \hat{\delta}(q_0, w) \in F \}.

Acceptance depends only on the state after reading all of $w$ . There is no stack and no unbounded memory: the current state is the entire memory.

Transition diagrams and tables

States are circles; accepting states have a double circle.
The start state has an incoming arrow with no source.
An edge $p \xrightarrow{a} q$ means $\delta(p,a) = q$ . Multiple symbols on one edge mean several transitions drawn together.
A transition table has rows = states, columns = symbols, entries = $\delta(q,a)$ . Mark the start and the accepting rows.

Dead states and unreachable states

A dead (reject sink) state $d \notin F$ satisfies $\delta(d,a) = d$ for every $a$ . Irreversible rejection can be represented by one dead sink; all hopeless states collapse to that sink on minimization.
An unreachable state is never entered from $q_0$ on any string. It does not affect $L(M)$ and can be removed.

How it works

Design patterns

Track a property of the prefix read so far that is finite-valued: length modulo $k$ , value modulo $k$ , progress toward a keyword, parity of a count, last few symbols.
Make one state per possible value of that property.
Mark accepting those values that mean "the string so far is in the language".
Fill every transition; add a dead state if the property can fail permanently.

Keyword / suffix pattern. For "strings ending with $w$ " where $|w| = m$ , keep the longest prefix of $w$ that is a suffix of the text read so far (the failure function idea from string matching). That needs at most $m+1$ states.

Modular arithmetic. For binary strings whose integer value is $0 \bmod k$ , states are residues $0,1,\ldots,k-1$ . Reading bit $b$ sends residue $r$ to $(2r+b) \bmod k$ .

Algorithms and pseudocode

Pseudocode uses sets and maps; $\delta[q][a]$ is the next state.

Text

DFA-ACCEPT(M, w)
1  q <- M.q0
2  for each symbol a in w, left to right
3      q <- M.delta[q][a]
4  return q in M.F

Time $\Theta(|w|)$ ; space $\Theta(1)$ beyond the machine description.

Text

DFA-LANGUAGE-NONEMPTY(M)
1  reach <- {M.q0};  work <- queue with M.q0
2  while work is not empty
3      p <- dequeue(work)
4      for each a in Sigma
5          r <- M.delta[p][a]
6          if r not in reach
7              add r to reach; enqueue r
8  return reach intersects M.F

Emptiness of a DFA language is decidable in linear time in the size of the machine (reachability).

Mathematical explanation

Myhill-Nerode (statement for design intuition)

Define $x \equiv_L y$ iff for every $z$ , $xz \in L \Leftrightarrow yz \in L$ . The equivalence classes of $\equiv_L$ are exactly the distinctions a DFA for $L$ must remember. $L$ is regular iff $\equiv_L$ has finitely many classes, and the minimal DFA has one state per class (see DFA Minimization).

Closure teaser

If $L$ and $M$ are DFA languages, so are $L \cup M$ , $L \cap M$ and $\overline{L}$ , by product constructions and flipping accepting states. Full proofs sit in Closure and Decision Properties of Regular Languages.

Worked examples

Example 1: binary value divisible by 3

Alphabet $\Sigma = \{0,1\}$ . Interpret $w$ as a binary integer ( $w = \varepsilon$ has value 0). States $q_0,q_1,q_2$ remember the value of the prefix modulo 3. Start and only accept: $q_0$ .

\delta(q_r, 0) = q_{(2r) \bmod 3}, \qquad \delta(q_r, 1) = q_{(2r+1) \bmod 3}.

State	on 0	on 1
$q_0$	$q_0$	$q_1$
$q_1$	$q_2$	$q_0$
$q_2$	$q_1$	$q_2$

Traces:

0: value 0, stay in $q_0$ , accept.
1: value 1, to $q_1$ , reject.
11: value 3, $q_0 \xrightarrow{1} q_1 \xrightarrow{1} q_0$ , accept.
10: value 2, to $q_2$ , reject.

Induction on the length shows that after reading $w$ the machine is in $q_r$ with $r = \mathrm{val}(w) \bmod 3$ , because appending bit $b$ maps the value $v$ to $2v + b$ .

DFA for binary strings with value divisible by 3 — Figure 1. DFA with states q0, q1, q2 for binary value modulo 3; q0 is start and accept; edges labelled 0 and 1 implement $\delta(q_r,b)=q_{(2r+b)\bmod 3}$ .

Example 2: strings ending with `01`

States remember the current progress toward the suffix 01:

State	Meaning	Accept?
$\varepsilon$	no progress	no
`0`	suffix is `0`	no
`01`	suffix is `01`	yes
`1`	suffix is `1` (but not `01`)	no

Transitions for a redundant four-state refinement of the canonical three-state suffix-progress automaton (the states labelled epsilon and 1 have equivalent future behaviour):

	0	1
$\varepsilon$	`0`	`1`
`0`	`0`	`01`
`01`	`0`	`1`
`1`	`0`	`1`

Check: 01 accepted; 001 accepted; 010 rejected; 1 rejected; every string of length at most 7 behaves as the predicate "ends with 01".

This DFA is correct but not minimal. States $\varepsilon$ and 1 behave identically: both go to 0 on 0 and to 1 on 1, and both reject. Merging them leaves 3 states, which is the minimum: the prefixes $\varepsilon$ , 0, 01 are pairwise distinguishable ( $\varepsilon$ and 0 by the continuation 1; either of them and 01 by the empty continuation). In general "ends with $w$ ", $|w| = m$ , needs exactly $m+1$ states.

Example 3: strings containing the substring `aba`

Alphabet $\{a,b\}$ . State $i$ means "the longest suffix of the input that is a prefix of aba has length $i$ "; state 3 means aba has already occurred, and it is an accepting sink.

State	on a	on b	Accept?
0	1	0	no
1	1	2	no
2	3	0	no
3	3	3	yes

The two failure edges decide the question. From state 1 on a the machine stays in 1 (the new a can start the pattern again), and from state 2 on b it returns to 0 (abb has no suffix that begins aba). Traces: abaa ends in 3 and is accepted; abba passes 1, 2, 0, 1 and is rejected; aababb reaches 3 at the fourth symbol and stays there. The four prefixes $\varepsilon$ , a, ab, aba are pairwise distinguishable, so 4 states is minimal.

Substring versus suffix. "Contains $w$ " has an accepting sink; "ends with $w$ " does not, because later symbols can destroy the match. Both need $m+1$ states. "Starts with $w$ " needs $m+2$ : the $m+1$ progress states plus a dead state for an early mismatch.

Example 4: two counters at once

Let $L = \{ w \in \{a,b\}^* \mid \#_a(w) \text{ even and } \#_b(w) \equiv 0 \pmod 3 \}$ . Track the pair $(\#_a \bmod 2, \#_b \bmod 3)$ : 6 states, start and only accept $(0,0)$ ; a flips the first component, b adds 1 to the second modulo 3. No two pairs are equivalent (pairs differing in the $a$ -parity are separated by a suitable string of $b$ s followed by nothing or by a, and similarly for the $b$ -count), so the minimal DFA has exactly $2 \times 3 = 6$ states. The same 6 states with accept set "first component 0 or second component 0" recognize the union, which also needs 6 states.

Example 5: counting DFAs

How many DFAs are there with the two states $X, Y$ , start state $X$ , over $\{a,b\}$ ? Each of the $2 \times 2 = 4$ table entries has 2 choices and $F$ is any of the 4 subsets: $2^4 \times 4 = 64$ . In general, with $n$ labelled states, a fixed start state and $|\Sigma| = m$ ,

\#\text{DFAs} = 2^{n} \cdot n^{nm}, \qquad \text{and } n \cdot 2^{n} \cdot n^{nm} \text{ if the start state may be any of the } n.

How many of the 64 accept $\emptyset$ ? Exactly those with no reachable accepting state. $F = \emptyset$ : all 16 tables. $F = \{Y\}$ : $Y$ must be unreachable, so both edges of $X$ loop on $X$ , while $Y$ 's two edges are free: 4 tables. $F$ containing $X$ always accepts $\varepsilon$ . Total $16 + 4 = 20$ . These 64 machines accept only 26 different languages, a reminder that counting machines is not counting languages.

Important properties and observations

A DFA has exactly one run on each string; acceptance is "final state in $F$ ".
Adding unreachable states does not change the language; removing a dead state may make $\delta$ partial (avoid in formal answers unless the problem allows incomplete DFAs).
Number of states is not unique for a language unless the DFA is minimal.
$L = \Sigma^*$ iff every reachable state is accepting; $L = \emptyset$ iff no accepting state is reachable.
DFAs and NFAs define the same class of languages; DFAs can need exponentially more states (see NFA and Subset Construction).

Minimal state counts to remember

Over $\Sigma = \{a, b\}$ unless stated. Every count is for a complete minimal DFA, so a dead state is included when one is needed.

Language	Minimal states	Why
$\lvert w \rvert = n$	$n+2$	lengths $0..n$ , plus dead for "too long"
$\lvert w \rvert \le n$	$n+2$	same states, different accept set
$\lvert w \rvert \ge n$	$n+1$	lengths $0..n-1$ , then an accepting sink
$\lvert w \rvert \bmod k = r$	$k$	residues of the length
$\#_a(w) \bmod k = r$	$k$	residues of the count
$\#_a \bmod p = r$ and $\#_b \bmod q = s$	$pq$	product; the same for "or" when $p,q\ge2$ and $0\le r<p$ , $0\le s<q$ ; trivial moduli can collapse the OR language
ends with $w$ , $\lvert w \rvert = m$	$m+1$	prefixes of $w$ , no sink
contains $w$ , $\lvert w \rvert = m$	$m+1$	prefixes of $w$ , accepting sink
starts with nonempty $w$ , $\lvert w \rvert=m\ge1$	$m+2$	prefixes of $w$ , accepting sink, dead state
first and last symbols equal (nonempty)	5	start, and two states for each first symbol
$k$ -th symbol from the end is $a$	$2^k$	must remember the last $k$ symbols
binary value divisible by $k = 2^t m$ , $m$ odd	$m + t$	the factor $2^t$ only needs the last $t$ bits

For starts-with, the empty prefix gives the universal language and needs one state.

The last row needs care. Divisibility by 3 needs 3 states, but divisibility by 4 needs only 3 (not 4): after padding with leading zeros, a number is a multiple of 4 iff its last two bits are 00. Thus accept epsilon and 0 as well as every string ending 00. The initial state is accepting; the three state classes are "epsilon, 0, or ends 00", "ends 10", and "ends 1". Divisibility by 6 needs $3 + 1 = 4$ , by 8 needs 4, by 12 needs 5, by 16 needs 5. These counts treat $\varepsilon$ as the value 0 and allow leading zeros; a question that forbids leading zeros adds states, so read it carefully.

Acceptance of the empty string. $\varepsilon \in L(M)$ iff $q_0 \in F$ . Use this as a one-second sanity check on every designed machine.

Complement needs a complete DFA. Swapping $F$ and $Q \setminus F$ recognizes $\Sigma^* \setminus L$ only when $\delta$ is total. On a partial diagram, first add the dead state; it then becomes accepting in the complement.

Common misconceptions.

"Missing transitions mean reject immediately." Formally $\delta$ is total; model missing arrows by a dead state.
"The machine accepts as soon as it visits an accept state." No: acceptance is checked only after the whole string is read (unless the problem explicitly asks for acceptance on a prefix).
"More states always mean a larger language." False; state count is about memory, not language size.

GATE examination perspective

SIMULATE CAREFULLY. Write the state after each symbol; do not skip.
MODULO MACHINES. Confirm the update rule $(2r+b) \bmod k$ for binary value; for decimal digits use $(10r+d) \bmod k$ .
SUFFIX LANGUAGES. Build the progress automaton; follow the particular table given: its redundant refinement sends 01 on 1 to 1, which is equivalent to $\varepsilon$ in the canonical minimized automaton.
COUNT THE STATES. Minimal state counts use Myhill-Nerode distinguishability: exhibit $n$ prefixes that are pairwise distinguishable for the lower bound and an $n$ -state DFA for the upper bound. Use the table of minimal counts above, and recheck the dead state.
"MINIMAL" WITH A DEAD STATE. Some questions count the dead state and some say "ignore the trap state". The table counts it; subtract 1 only when the question says so.
BINARY DIVISIBILITY. Divisible by $2^t m$ needs $m + t$ states, not $2^t m$ . Decimal digits use $(10r + d) \bmod k$ .
COUNTING MACHINES. "How many DFAs with $n$ states" counts tables and accept sets ( $2^n n^{nm}$ with a fixed start), not languages.
CONTAINS VERSUS ENDS WITH. Check whether the accept state is a sink. A sink is right for "contains", wrong for "ends with".
DEAD STATE. If the question's diagram omits transitions, say that a dead sink is assumed.

Summary

Alphabets, Strings and Languages: prerequisite.
NFA, Epsilon-NFA and Subset Construction: dependent. Nondeterminism and powerset construction.
DFA Minimization: dependent. Unique minimal DFA.
Lexical Analysis: related. DFAs as token recognizers.
Sequential Circuit Design: related. Finite-state control in hardware.

Deterministic Finite Automata

Introduction

Prerequisites

Core concepts

Formal definition

How a DFA processes a string

Transition diagrams and tables

Dead states and unreachable states

How it works

Design patterns

Algorithms and pseudocode

Mathematical explanation

Myhill-Nerode (statement for design intuition)

Closure teaser

Worked examples

Example 1: binary value divisible by 3

Example 2: strings ending with `01`

Example 3: strings containing the substring `aba`

Example 4: two counters at once

Example 5: counting DFAs

Important properties and observations

Minimal state counts to remember

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Formal definition

How a DFA processes a string

Transition diagrams and tables

Dead states and unreachable states

How it works

Design patterns

Algorithms and pseudocode

Mathematical explanation

Myhill-Nerode (statement for design intuition)

Closure teaser

Worked examples

Example 1: binary value divisible by 3

Example 2: strings ending with 01

Example 3: strings containing the substring aba

Example 4: two counters at once

Example 5: counting DFAs

Important properties and observations

Minimal state counts to remember

GATE examination perspective

Summary

Related topics

Sources

Next steps

Example 2: strings ending with `01`

Example 3: strings containing the substring `aba`