# Lecture 14. Automata theory

## Overview

This is the final topic of the course, and it is where the strands we have been
spinning finally braid together. Automata theory is built from sets and tuples
(Lecture 2), from **functions viewed as a special kind of relation** (Lecture 3),
from the **Boolean/combinational logic** of gates and adders (Lecture 5), and from
the **propositional connectives** whose set-theoretic shadows — union,
intersection, complement — reappear here as operations on languages (Lecture 6).
What is genuinely new is a single idea that none of those earlier chapters
possessed: **state**, a finite memory of the relevant past that lets a device
behave differently on the same input depending on where it currently is.

We begin, as the slides do, with a concrete hardware question — the difference
between **combinational** and **sequential** logic — and then peel away wires and
gates until only the essential mechanism remains: a control unit that occupies one
of finitely many states and moves between them as it reads symbols. That
abstraction is the **finite automaton**, the central object of this chapter.

From the hardware contrast we build up, in order: the vocabulary of **alphabets,
strings, and languages**; the general **abstract machine** (tape, reader, control
unit); the **deterministic finite automaton (DFA)** with its extended transition
function $\hat\delta$, its **runs**, its notion of **acceptance**, and the
**language** $L(M)$ it recognises; the output-producing **Mealy** and **Moore**
machines; the **nondeterministic** automaton (NFA) with $\varepsilon$-moves and the
**subset construction** that flattens it back to a DFA; the identification of
finite automata with the **regular languages** and **regular expressions** (Kleene)
and the **closure properties** of that class; and finally the **pumping lemma**,
which lets us *prove* that some languages — famously $\{0^n1^n\}$ — lie beyond the
reach of any finite automaton. We close with a signpost toward the richer machines
(pushdown automata, Turing machines) that lie past the horizon of this course.

Unlike earlier drafts of these notes, this chapter proves what it states. Every
theorem comes with a complete argument, and every automaton comes with a trace or
an induction that certifies it does what we claim. Deliberately out of scope:
Turing machines beyond a mention, and the DFA-minimisation algorithm
(Myhill–Nerode is noted but not developed).

---

## 14.1 Combinational versus sequential logic

Digital circuits split into two kinds according to what their outputs depend on,
and the split is exactly the doorway into automata theory.

> **Definition (combinational logic).** A **combinational** circuit is one whose
> outputs are determined *only by the current inputs*. It has **no memory**:
> present the same input bits and you always get the same output bits.

This is precisely the world of Lecture 5. A combinational circuit *computes a
Boolean function* $f:\{0,1\}^n\to\{0,1\}^m$, and everything we said there —
truth tables, canonical normal forms, Karnaugh-map minimisation — describes it
completely. Typical building blocks are **adders**, **subtractors**,
**multiplexers**, **encoders**, **decoders**, and the arithmetic-logic unit
(**ALU**) assembled from them.

*Adder example.* A **full adder** turns three input bits — two operands $a,b$ and a
carry-in $c_{\text{in}}$ — into a sum bit and a carry-out that are Boolean functions
of those inputs *alone*:

$$
s = a \oplus b \oplus c_{\text{in}}, \qquad c_{\text{out}} = (a\wedge b)\vee(a\wedge c_{\text{in}})\vee(b\wedge c_{\text{in}}).
$$

Chaining $n$ full adders (a ripple-carry adder) is still combinational: the output
word is a fixed function of the current input word. Nowhere is any past input
remembered.

> **Definition (sequential logic).** A **sequential** circuit is one whose outputs
> depend on the current inputs *and* on an internal **state** that summarises
> relevant past inputs. The state is held in memory elements (**flip-flops**), and
> updates are typically paced by a **clock** signal.

Because the same input can now produce different outputs depending on the stored
state, sequential circuits can **count**, **remember**, **detect patterns over
time**, and **implement protocols** — none of which a combinational circuit can do.
A pocket calculator's "+" key does something different depending on what you typed
before; a turnstile behaves differently locked versus unlocked; a traffic light
cycles. Each needs memory of the past.

![State diagram of a turnstile: a coin moves it from Locked to Unlocked and a push moves it back — behaviour depends on the current state](img/l14_state_idea.png)

**The flip-flop stores one bit of state.** The atomic memory element of sequential
hardware is the **flip-flop**: a one-bit register that holds a $0$ or a $1$ between
clock ticks and updates on the tick according to its inputs. A circuit with $k$
flip-flops has $2^k$ possible stored configurations, i.e. **$2^k$ states**. This is
the physical incarnation of the abstract "state" of an automaton: *a finite
automaton with $n$ states can be realised by a sequential circuit using
$\lceil \log_2 n\rceil$ flip-flops plus combinational logic to compute the next
state and the output.* Combinational logic (Lecture 5) and sequential logic
(this lecture) are therefore not rivals but layers: the combinational part
computes the transition function, the flip-flops hold the state between ticks.

**Remark (the pivot word is *state*).** The instant a circuit needs to "remember
where it is", it becomes sequential, and the natural mathematical model of "a
device that lives in one of finitely many states" is the finite automaton. Automata
theory is, in effect, the *algebra of sequential behaviour* — the abstract theory
of what memory-bounded machines can and cannot do.

---

## 14.2 Alphabets, strings, and languages

Before we can say what a machine reads or accepts, we need vocabulary for its
input. All of it is elementary set theory (Lecture 2) applied to sequences.

> **Definition (alphabet, string, length).** An **alphabet** $\Sigma$ is a finite,
> non-empty set whose elements are called **symbols**. A **string** (or **word**)
> over $\Sigma$ is a finite sequence of symbols from $\Sigma$. The **length** $|w|$
> of a string $w$ is the number of symbols in it. The unique string of length $0$
> is the **empty string**, written $\varepsilon$.

For example, over $\Sigma=\{0,1\}$ the strings of length $\le 2$ are
$\varepsilon,\ 0,\ 1,\ 00,\ 01,\ 10,\ 11$. Note $|\varepsilon|=0$ and, e.g.,
$|0110|=4$.

> **Definition (concatenation).** The **concatenation** of strings $u=a_1\cdots a_m$
> and $v=b_1\cdots b_n$ is $uv=a_1\cdots a_m b_1\cdots b_n$, of length $m+n$.
> Concatenation is associative, and $\varepsilon$ is its identity:
> $\varepsilon w = w\varepsilon = w$. We write $w^k$ for $w$ concatenated with
> itself $k$ times, with $w^0=\varepsilon$.

**Remark (a monoid, echoing Lecture 3).** The set of all strings under
concatenation, with identity $\varepsilon$, is a **monoid** — an associative
operation with a unit. This is the same algebraic pattern you met when composing
relations and functions in Lecture 3; there, composition of functions was
associative with the identity function as unit. String concatenation is that
structure made concrete.

> **Definition ($\Sigma^\ast$, $\Sigma^+$, $\Sigma^k$).** $\Sigma^k$ is the set of
> all strings of length exactly $k$. The **Kleene star**
> $\Sigma^\ast=\bigcup_{k\ge 0}\Sigma^k$ is the set of **all** finite strings over
> $\Sigma$ (including $\varepsilon$); $\Sigma^+=\bigcup_{k\ge 1}\Sigma^k$ excludes
> $\varepsilon$.

Substrings, prefixes, and suffixes are defined the obvious way: $x$ is a **prefix**
of $w$ if $w=xy$ for some $y$, a **suffix** if $w=yx$ for some $y$, and a
**substring** if $w=uxv$ for some $u,v$.

> **Definition (language).** A **language** over $\Sigma$ is any subset
> $L\subseteq\Sigma^\ast$.

A language is just a *set of strings* — possibly finite ($\{01,10\}$), possibly
infinite ($\{0^n1^n:n\ge 0\}$), possibly empty ($\varnothing$), possibly all of
$\Sigma^\ast$. Because languages are sets, the Boolean operations of Lecture 6
apply verbatim: **union** $L_1\cup L_2$, **intersection** $L_1\cap L_2$, and
**complement** $\overline{L}=\Sigma^\ast\setminus L$. Two operations are special to
strings:

- **Concatenation of languages:** $L_1L_2=\{uv : u\in L_1,\ v\in L_2\}$.
- **Kleene star of a language:** $L^\ast=\bigcup_{k\ge 0}L^k$, where $L^0=\{\varepsilon\}$
  and $L^{k+1}=L^kL$. Thus $L^\ast$ is all concatenations of zero or more strings
  from $L$.

**Common pitfall.** $\varepsilon$ (the empty *string*) and $\varnothing$ (the empty
*language*) are different objects, and both differ from $\{\varepsilon\}$ (the
language containing only the empty string). Note $L\varnothing=\varnothing$ but
$L\{\varepsilon\}=L$, and $\varnothing^\ast=\{\varepsilon\}$.

The central question of the chapter can now be phrased crisply: **which languages
can a finite-memory machine recognise?**

---

## 14.3 The abstract machine and the idea of state

We first describe a general **abstract machine**, so that stronger machines
appear later as the same picture with more memory. It consists of an **input tape**
holding a string of symbols, a **reader** (head) positioned over one cell, and a
**control unit** that is always in some internal state. In one step the machine may
read the current symbol, inspect and change auxiliary memory, change the
control-unit state, possibly write to the tape, and move the reader.

> **Definition (configuration).** A snapshot of an abstract machine at one instant —
> its **configuration** — is the triple (current control state, current memory
> contents, position of the reader). A **computation** is a sequence of
> configurations, each obtained from the previous one by a single legal step.

> **Definition (finite-state machine).** A **finite-state machine** (finite
> automaton) is the most restricted such machine: it has **no auxiliary memory
> beyond its control state**, its reader moves **one symbol per step in a single
> direction** (left to right), and its control unit has a **finite** set of states
> $S=\{s_0,s_1,\dots,s_N\}$. Its control may be **deterministic** (each situation
> has exactly one next move) or **nondeterministic** (a situation may permit
> several).

The deck writes a general finite machine as the seven-tuple

$$
M=(S,\; I,\; O,\; f,\; g,\; s_0,\; F),
$$

where $S$ is the state set, $I$ the input alphabet, $O$ the output alphabet, $f$ the
transition ("movement") function, $g$ the output ("exit") function, $s_0$ the start
state, and $F$ the set of final states. This form covers machines that *produce
output* (Mealy/Moore, §14.6). When we care only *whether* a string is accepted — not
what is printed — we discard $O$ and $g$ and obtain the **acceptor** studied next.

---

## 14.4 Deterministic finite automata

> **Definition (DFA).** A **deterministic finite automaton** is a five-tuple
>

$$
M=(Q,\Sigma,\delta,q_0,F),
$$

> where
> - $Q$ is a finite set of **states**;
> - $\Sigma$ is a finite **input alphabet**;
> - $\delta : Q \times \Sigma \to Q$ is the **transition function**: given the current
>   state and the symbol just read, it names the unique next state;
> - $q_0 \in Q$ is the **start state**;
> - $F \subseteq Q$ is the set of **accepting (final) states**.

The word *deterministic* means $\delta$ is a **total function**: for every state
and every input symbol there is **exactly one** next state — no choices, no missing
moves. A DFA has no output alphabet; its "answer" is simply whether it halts in an
accepting state.

**Cross-reference (Lecture 3).** The transition function $\delta$ is exactly a
*function*, and — as Lecture 3 established — a function is a special binary relation
$\delta\subseteq (Q\times\Sigma)\times Q$ that is **total** (defined on every input
pair) and **single-valued** (at most one output). Determinism is nothing more than
"$\delta$ is a genuine function, not merely a relation." When we drop those two
conditions in §14.7 we get exactly the relational — nondeterministic — machine.

> **Definition (transition table).** Because $\delta$ has a small finite domain, we
> list it completely as a **transition table** with one row per state and one column
> per input symbol; the entry is the next state. The start state is marked with an
> arrow $\rightarrow$ and each accepting state with a star $\ast$.

> **Definition (state diagram).** The same $\delta$ is drawn as a labelled directed
> graph (Lecture 10): one **node** per state, and an **edge**
> $q \xrightarrow{a} q'$ for each transition $\delta(q,a)=q'$. The start state has
> an incoming arrow "from nowhere"; accepting states are drawn as **double
> circles**. Reading a string means walking the graph, following the edge labelled
> by each symbol in turn.

### The extended transition function

$\delta$ tells us what one symbol does. To speak of whole strings we lift it to
$\hat\delta:Q\times\Sigma^\ast\to Q$.

> **Definition (extended transition function).** Define $\hat\delta$ by recursion on
> the length of the string:
>

$$
\hat\delta(q,\varepsilon)=q, \qquad \hat\delta(q, wa)=\delta\big(\hat\delta(q,w),\,a\big),
$$

> where $w\in\Sigma^\ast$ and $a\in\Sigma$.

So $\hat\delta(q_0,w)$ is the single state reached after reading all of $w$ from
$q_0$. The following bookkeeping lemma — that $\hat\delta$ respects concatenation —
is used repeatedly (in the product and subset constructions, and in the pumping
lemma), so we prove it once.

> **Lemma 14.1 (concatenation law for $\hat\delta$).** For every state $q$ and all
> strings $u,v\in\Sigma^\ast$,
>

$$
\hat\delta(q,uv)=\hat\delta\big(\hat\delta(q,u),\,v\big).
$$

*Proof.* Fix $q$ and $u$; induct on $|v|$.

*Base* $|v|=0$, i.e. $v=\varepsilon$. Then $uv=u$, so the left side is
$\hat\delta(q,u)$. The right side is $\hat\delta(\hat\delta(q,u),\varepsilon)$,
which equals $\hat\delta(q,u)$ by the first clause of the definition. The two sides
agree.

*Inductive step.* Suppose the identity holds for a string $w$; we prove it for
$v=wa$ with $a\in\Sigma$. Using the definition of $\hat\delta$, then the induction
hypothesis, then the definition again:

$$
\hat\delta(q,u\,wa) =\hat\delta(q,(uw)a) =\delta\big(\hat\delta(q,uw),a\big) \overset{\text{IH}}{=}\delta\big(\hat\delta(\hat\delta(q,u),w),a\big) =\hat\delta\big(\hat\delta(q,u),wa\big).
$$

This is the claim for $v=wa$, completing the induction. $\blacksquare$

### Runs, acceptance, and the language of a DFA

Fix a DFA $M=(Q,\Sigma,\delta,q_0,F)$ and an input $w=a_1a_2\cdots a_n$.

> **Definition (run).** The **run** of $M$ on $w$ is the sequence of states
> $r_0,r_1,\dots,r_n$ with $r_0=q_0$ and $r_i=\delta(r_{i-1},a_i)$ for
> $1\le i\le n$. Equivalently $r_i=\hat\delta(q_0,a_1\cdots a_i)$. Because $M$ is
> deterministic, **each string has exactly one run.**

> **Definition (acceptance and language).** $M$ **accepts** $w$ if its run ends in
> an accepting state, $\hat\delta(q_0,w)\in F$; otherwise $M$ **rejects** $w$. The
> **language recognised** by $M$ is
>

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

> **Definition (regular language — first form).** A language $L$ is **regular** if
> $L=L(M)$ for some DFA $M$.

**Design principle.** Building a DFA for a target language means choosing states
that record *exactly the finite amount of information about the input read so far*
that is needed to decide acceptance — and no more, since only finitely many states
are allowed. Each state is an **equivalence class of histories**: two input
prefixes that must be treated identically from now on may share a state. (This idea,
made precise, is the **Myhill–Nerode theorem**, which we only name here.)

---

## 14.5 Worked DFA designs

We now design and *verify* several DFAs. Each verification is either a full trace or
an induction certifying $L(M)$ is what we claim.

### Example A — even number of $1$s

**Task.** Over $\Sigma=\{0,1\}$, accept exactly the strings with an **even** number
of $1$s (zero is even, so $\varepsilon$ is accepted).

**Design idea.** The only fact we must remember is the *parity* of the count of
$1$s. Parity has two values, so two states suffice. Reading $0$ leaves parity
unchanged; reading $1$ flips it.

**Formal definition.**

$$
Q=\{q_{\text{e}},q_{\text{o}}\},\quad \Sigma=\{0,1\},\quad q_0=q_{\text{e}},\quad F=\{q_{\text{e}}\},
$$

| State | on `0` | on `1` |
|---|---|---|
| $\rightarrow\ \ast\ q_{\text{e}}$ | $q_{\text{e}}$ | $q_{\text{o}}$ |
| $q_{\text{o}}$ | $q_{\text{o}}$ | $q_{\text{e}}$ |

**State diagram (in words).** Two nodes. $q_{\text{e}}$ is a double circle with the
start arrow into it; $q_{\text{o}}$ is a single circle. Each state has a self-loop
labelled `0`. Two arrows labelled `1` cross between the states, one each way.

![DFA accepting an even number of 1s: states "even" (accepting) and "odd", each with a 0 self-loop and 1-edges crossing between them](img/l14_dfa_even.png)

**Trace on `1001`** (two $1$s, should accept):

| Step | State before | Symbol | State after |
|---|---|---|---|
| start | — | — | $q_{\text{e}}$ |
| 1 | $q_{\text{e}}$ | `1` | $q_{\text{o}}$ |
| 2 | $q_{\text{o}}$ | `0` | $q_{\text{o}}$ |
| 3 | $q_{\text{o}}$ | `0` | $q_{\text{o}}$ |
| 4 | $q_{\text{o}}$ | `1` | $q_{\text{e}}$ |

Ends in $q_{\text{e}}\in F$: **accepted.** On `1011` (three $1$s) the run is
$q_{\text{e}}\to q_{\text{o}}\to q_{\text{o}}\to q_{\text{e}}\to q_{\text{o}}$,
ending outside $F$: **rejected.** Both correct.

We can do better than spot checks and *prove* correctness.

> **Proposition 14.2.** For every $w\in\{0,1\}^\ast$, $\hat\delta(q_{\text{e}},w)=q_{\text{e}}$
> if $w$ has an even number of $1$s, and $=q_{\text{o}}$ otherwise. Consequently
> $L(M)=\{w:\#_1(w)\text{ is even}\}$, where $\#_1(w)$ is the number of $1$s in $w$.

*Proof.* Induct on $|w|$. *Base:* $w=\varepsilon$ has $\#_1=0$ (even) and
$\hat\delta(q_{\text{e}},\varepsilon)=q_{\text{e}}$. *Step:* write $w=xa$ and assume
the claim for $x$. If $a=0$ then $\#_1(w)=\#_1(x)$ and, since $\delta(q,0)=q$ for
both states, $\hat\delta(q_{\text{e}},xa)=\hat\delta(q_{\text{e}},x)$; the parity and
the state both stay put, so the correspondence persists. If $a=1$ then
$\#_1(w)=\#_1(x)+1$ (parity flips) and $\delta(\,\cdot\,,1)$ swaps the two states
(state flips); flipping both sides of the induction hypothesis preserves the
correspondence. Finally $w\in L(M)$ iff $\hat\delta(q_{\text{e}},w)=q_{\text{e}}\in F$
iff $\#_1(w)$ is even. $\blacksquare$

### Example B — ends in `01`

**Task.** Over $\{0,1\}$, accept the strings that **end in `01`**.

**Design idea (suffix matching).** Let each state record *the longest suffix of the
input read so far that is a prefix of the pattern* `01`. The prefixes of `01` are
$\varepsilon$, `0`, `01`, giving three states: $A$ (no useful suffix), $B$ (ends in
`0`), $C$ (ends in `01`, accepting).

| State | on `0` | on `1` |
|---|---|---|
| $\rightarrow\ A$ | $B$ | $A$ |
| $B$ | $B$ | $C$ |
| $\ast\ C$ | $B$ | $A$ |

**Reading the table.** From $B$ ("...0") a further `0` still ends in `0` ($\to B$);
a `1` completes `01` ($\to C$). From $C$ ("...01") a `0` ends in `0` ($\to B$); a
`1` ends in `11`, no useful suffix ($\to A$).

**Traces.** `0101`: $A\to B\to C\to B\to C$ (accept — indeed ends `01`). `011`:
$A\to B\to C\to A$ (reject — ends `11`).

**Remark (a template).** Example B generalises: to accept strings *ending in a fixed
pattern* $p$, use one state per prefix of $p$ (the states of the **Knuth–Morris–Pratt**
string matcher). To accept strings *containing* $p$ as a substring, do the same but
make the "matched all of $p$" state **absorbing and accepting** — see Example C.

### Example C — contains the substring `001`

**Task.** Over $\{0,1\}$, accept every string that has `001` **somewhere** inside.

**Design idea.** Track progress toward matching `001`; once matched, latch into an
accepting sink.

| State | meaning | on `0` | on `1` |
|---|---|---|---|
| $\rightarrow\ S_0$ | no progress | $S_1$ | $S_0$ |
| $S_1$ | seen `0` | $S_2$ | $S_0$ |
| $S_2$ | seen `00` | $S_2$ | $S_3$ |
| $\ast\ S_3$ | seen `001` (done) | $S_3$ | $S_3$ |

**Two subtle entries.** From $S_2$ ("...00") reading `0` keeps the last two symbols
`00`, so we stay at $S_2$ (not fall back). From $S_1$ ("...0") reading `1` gives
suffix `01`, which shares no prefix with `001`, so we reset to $S_0$.

**Trace on `01001`** (contains `001` at positions 3–5): $S_0\xrightarrow{0}S_1 \xrightarrow{1}S_0\xrightarrow{0}S_1\xrightarrow{0}S_2\xrightarrow{1}S_3$ — accept.
**Trace on `0100`** (no `001`): $S_0\to S_1\to S_0\to S_1\to S_2$ — reject. Correct.

**Common pitfall.** A frequent bug is sending $S_2$ back to $S_0$ or $S_1$ on
reading `0`. But `...000` still ends in `00`, so we must *stay* at $S_2$; forgetting
this makes the DFA miss matches like `0001`. Always ask: *after this symbol, what is
the longest pattern-prefix that is now a suffix of the input?*

### Example D — binary numbers divisible by $3$

**Task.** Over $\{0,1\}$, reading a binary numeral **most-significant bit first**,
accept exactly those whose value is divisible by $3$. (Take $\varepsilon$ to denote
$0$, which is divisible by $3$.)

**Design idea (running remainder).** Let the state be the value read so far *modulo*
$3$: states $r_0,r_1,r_2$. Appending a bit $b$ changes the value $n$ to $2n+b$, so
the remainder $r$ becomes $(2r+b)\bmod 3$. Compute all six entries:

- $r_0$: $b=0\to 0$, $b=1\to 1$;
- $r_1$: $b=0\to (2)\to r_2$, $b=1\to (3)\equiv 0\to r_0$;
- $r_2$: $b=0\to (4)\equiv 1\to r_1$, $b=1\to (5)\equiv 2\to r_2$.

| State | on `0` | on `1` |
|---|---|---|
| $\rightarrow\ \ast\ r_0$ | $r_0$ | $r_1$ |
| $r_1$ | $r_2$ | $r_0$ |
| $r_2$ | $r_1$ | $r_2$ |

**Traces.** `110` $=6$: $r_0\to r_1\to r_0\to r_0$ — accept ($6=3\cdot2$).
`1001` $=9$: $r_0\to r_1\to r_2\to r_1\to r_0$ — accept ($9=3\cdot3$).
`101` $=5$: $r_0\to r_1\to r_2\to r_2$ — reject ($5\bmod3=2$). All correct.

> **Proposition 14.3.** After reading numeral $w$, the DFA of Example D is in state
> $r_j$ where $j=\mathrm{value}(w)\bmod 3$.

*Proof.* Induct on $|w|$. Base $w=\varepsilon$: value $0$, state $r_0$. Step:
$w=xb$. By IH the state after $x$ is $r_{j}$ with $j=\mathrm{value}(x)\bmod 3$. Then
$\mathrm{value}(xb)=2\,\mathrm{value}(x)+b$, so
$\mathrm{value}(xb)\bmod3=(2j+b)\bmod3$, which is exactly the column the table
follows from $r_j$ on $b$. Hence the state after $xb$ is $r_{(2j+b)\bmod 3}$. $\blacksquare$

Since $F=\{r_0\}$, acceptance holds iff $\mathrm{value}(w)\equiv 0\pmod 3$, as
required. **Remark.** The same trick — "state = residue of a running quantity" —
gives DFAs for divisibility by any fixed modulus and for many counting conditions.

### Example E — a "dead state" and totality

**Task.** Accept strings that **begin with `1`**.

| State | on `0` | on `1` |
|---|---|---|
| $\rightarrow\ q_{\text{start}}$ | $q_{\text{dead}}$ | $q_{\text{yes}}$ |
| $\ast\ q_{\text{yes}}$ | $q_{\text{yes}}$ | $q_{\text{yes}}$ |
| $q_{\text{dead}}$ | $q_{\text{dead}}$ | $q_{\text{dead}}$ |

Once the first symbol is seen the verdict is fixed, so $q_{\text{yes}}$ and
$q_{\text{dead}}$ are **absorbing** (all their edges are self-loops).

**Common pitfall (totality).** A DFA's $\delta$ must be defined for *every*
(state, symbol) pair. When a partial design "has no move" for some case — here, a
string starting with `0` should never be accepted — you must add an explicit
**dead** (trap) state that absorbs all such inputs and is non-accepting. Diagrams
often omit the dead state for readability, but formally it is present. Forgetting it
turns your DFA into an NFA (or into nonsense).

---

## 14.6 Machines with output: Mealy and Moore

DFAs answer a yes/no question. Real sequential circuits usually also *emit output*
as they run (think of a controller driving actuators). Adding an output alphabet
$\Delta$ and an output function to the finite automaton gives a **finite-state
transducer**, and there are two standard flavours, distinguished by *where the
output lives.* (There are no accepting states here: a transducer transforms an input
string into an output string.)

> **Definition (Moore machine).** A **Moore machine** is
> $M=(Q,\Sigma,\Delta,\delta,\lambda,q_0)$ where output depends only on the
> **current state**, $\lambda:Q\to\Delta$. Passing through states $r_0,r_1,\dots,r_n$
> on an input of length $n$, it emits $\lambda(r_0)\lambda(r_1)\cdots\lambda(r_n)$ —
> one symbol per state entered, including an initial output *before any input*,
> hence $n+1$ output symbols.

> **Definition (Mealy machine).** A **Mealy machine** has the same shape but its
> output depends on the current state **and** the input symbol, so output is attached
> to **transitions**: $\lambda:Q\times\Sigma\to\Delta$. On an input of length $n$ it
> emits exactly $n$ output symbols, one per transition.

Both are captured by the transducer tuple $M=(S,I,O,f,g,s_0,F)$, in which $F$ is left unused because a transducer has no accepting states: $f$ is the transition
function $\delta$, $g$ is the output function $\lambda$, and $O=\Delta$. The sole difference
is whether $g$ may read the current input symbol (Mealy) or not (Moore).

### Shared example — a running-parity reporter

Reuse the parity machine of Example A, but now *report* the running parity of $1$s
after each symbol instead of only accepting at the end. States $E$ ("even so far")
and $O$ ("odd so far"); output alphabet $\{0,1\}$ (report $0$ for even, $1$ for odd).

![The same running-parity machine as Moore (output attached to each state) and as Mealy (output attached to each edge)](img/l14_moore_mealy.png)

**Moore version** (output labels the state, $\lambda(E)=0,\ \lambda(O)=1$):

| State | output $\lambda$ | on `0` | on `1` |
|---|---|---|---|
| $\rightarrow E$ | `0` | $E$ | $O$ |
| $O$ | `1` | $O$ | $E$ |

On input `1011` it visits $E,O,O,E,O$ and prints `01101` (the leading `0` is $E$'s
output before any symbol is read).

**Mealy version** (output labels the transition — report the parity *after* the
step):

| State | on `0` (next / out) | on `1` (next / out) |
|---|---|---|
| $\rightarrow E$ | $E$ / `0` | $O$ / `1` |
| $O$ | $O$ / `1` | $E$ / `0` |

On the same input `1011` it prints `1101` — the Moore output *without* the initial
symbol.

**What the comparison shows.** Moore output is stable while the machine sits in a
state (convenient in hardware, where the output is just a function of the flip-flop
contents) and carries one extra initial symbol. Mealy output reacts on the same step
the input arrives and often needs fewer states. The two are **equivalent in power**:

> **Theorem 14.4 (Mealy $\Leftrightarrow$ Moore, informal).** For every Moore
> machine there is a Mealy machine producing the same output (minus the initial
> symbol) on every input, and vice versa.

*Construction sketch.* *Moore $\to$ Mealy:* set the Mealy output on the transition
*into* a state to that state's Moore output, i.e. $\lambda_{\text{Mealy}}(q,a)= \lambda_{\text{Moore}}(\delta(q,a))$. *Mealy $\to$ Moore:* split each state into
copies tagged by the output symbol most recently produced, so "which output to
emit" becomes a property of the (new) state; the number of states grows by at most a
factor of $|\Delta|$. Both directions are routine inductions on input length, which
we omit. $\square$

**Cross-reference (sequential circuits).** A Mealy/Moore machine *is* the
mathematical model of the sequential circuit of §14.1: the flip-flops store the
state $q$, one block of combinational logic (Lecture 5) computes the next state
$\delta(q,a)$ from the stored state and the current input, and a second block
computes the output $\lambda$. Moore outputs depend on the register only; Mealy
outputs also read the current input wire.

---

## 14.7 Nondeterministic finite automata

Determinism forces exactly one move per (state, symbol). Relaxing that gives a model
that is frequently far easier to design.

> **Definition (NFA).** A **nondeterministic finite automaton** is a five-tuple
> $N=(Q,\Sigma,\delta,q_0,F)$ where the transition function returns a **set** of
> states,
>

$$
\delta:Q\times(\Sigma\cup\{\varepsilon\})\to 2^{Q},
$$

> allowing (i) **several** next states on a symbol, (ii) **no** next state (the
> empty set — a dead end), and (iii) **$\varepsilon$-transitions**
> $\delta(q,\varepsilon)$ that change state **without reading input**. Everything
> else is as for a DFA.

**Cross-reference (Lecture 3).** Where a DFA's $\delta$ was a *function*, an NFA's is
a general *relation* $\Delta\subseteq Q\times(\Sigma\cup\{\varepsilon\})\times Q$
presented as a set-valued map. This is precisely the loosening — "drop
single-valuedness and totality" — foreshadowed in §14.4.

> **Definition (acceptance for NFAs).** $N$ **accepts** $w$ if there exists *at least
> one* run — one way of resolving the choices, possibly taking $\varepsilon$-moves —
> that reads all of $w$ and ends in an accepting state. Think of it as **existential**:
> the machine accepts iff *some* computational path succeeds. ($L(N)$ is defined as
> the set of accepted strings, exactly as before.)

To make "reachable via $\varepsilon$-moves" precise we need one notion.

> **Definition ($\varepsilon$-closure).** For a set $S\subseteq Q$, the
> **$\varepsilon$-closure** $E(S)$ is the set of all states reachable from some state
> of $S$ by following zero or more $\varepsilon$-transitions. (Formally, the smallest
> set containing $S$ and closed under $q\mapsto\delta(q,\varepsilon)$.)

We can now give the NFA analogue of $\hat\delta$, this time set-valued:

$$
\hat\delta_N(q,\varepsilon)=E(\{q\}),\qquad \hat\delta_N(q,wa)=E\!\Big(\textstyle\bigcup_{p\in \hat\delta_N(q,w)}\delta(p,a)\Big),
$$

and $N$ accepts $w$ iff $\hat\delta_N(q_0,w)\cap F\neq\varnothing$. (If there are no
$\varepsilon$-moves, $E$ is the identity and the formulas simplify.)

### Example F — "ends in `01`", the easy way

An NFA can *guess* where the final `01` begins:

| State | on `0` | on `1` |
|---|---|---|
| $\rightarrow\ p_0$ | $\{p_0,p_1\}$ | $\{p_0\}$ |
| $p_1$ | $\varnothing$ | $\{p_2\}$ |
| $\ast\ p_2$ | $\varnothing$ | $\varnothing$ |

State $p_0$ loops on every symbol (staying in "still reading the bulk"); on a `0` it
*also* forks into $p_1$, betting that this `0` starts the final `01`. From $p_1$ a
`1` confirms the bet and reaches accepting $p_2$; any other continuation from $p_1$
or $p_2$ dies. The string is accepted iff *some* fork survives to the end in $p_2$,
i.e. iff the last two symbols are `01`.

**Remark (why NFAs matter — succinctness).** Consider $L_k=\{w\in\{0,1\}^\ast : \text{the } k\text{-th symbol from the end is } 1\}$. An NFA needs only $k+1$ states (guess the
position, then count $k$ more symbols). But *any* DFA for $L_k$ needs at least $2^k$
states, because it must remember the last $k$ symbols — the $2^k$ possible windows
are pairwise distinguishable. Nondeterminism buys **exponential succinctness**, even
though — as we now prove — it buys **no extra recognising power.**

---

## 14.8 The subset construction: NFA $\to$ DFA

The pivotal theorem of the chapter says nondeterminism is a convenience, not a new
capability. The construction is the natural one: run the NFA and, at each step, track
*the set of all states it could currently be in.* That set is a single DFA state.

![Subset construction turning an NFA into a DFA: each DFA state is a set of NFA states, and a set is accepting if it contains an NFA accepting state](img/l14_subset.png)

> **Theorem 14.5 (Rabin–Scott, subset construction).** For every NFA
> $N=(Q,\Sigma,\delta,q_0,F)$ there is a DFA $D$ with $L(D)=L(N)$.

*Proof.* We first treat the case with **no $\varepsilon$-transitions**, then note the
one change needed for the general case.

**Construction.** Define $D=(Q_D,\Sigma,\Delta,S_0,F_D)$ by

$$
Q_D=2^{Q},\qquad S_0=\{q_0\},\qquad \Delta(S,a)=\bigcup_{q\in S}\delta(q,a),\qquad F_D=\{\,S\subseteq Q : S\cap F\neq\varnothing\,\}.
$$

$D$ is a legitimate DFA: $\Delta$ is a total single-valued function on
$Q_D\times\Sigma$ (a union of sets is one well-defined set, even when it is empty),
and $Q_D$ is finite (it has $2^{|Q|}$ elements). Write $\hat\Delta$ for $D$'s
extended transition function.

**Key lemma.** For every $w\in\Sigma^\ast$,

$$
\hat\Delta(\{q_0\},w)=\hat\delta_N(q_0,w),
$$

i.e. the DFA state after reading $w$ is *exactly* the set of NFA states reachable on
$w$. We prove it by induction on $|w|$.

*Base* $w=\varepsilon$: $\hat\Delta(\{q_0\},\varepsilon)=\{q_0\}$ by definition of
$\hat\Delta$, and $\hat\delta_N(q_0,\varepsilon)=\{q_0\}$ (no $\varepsilon$-moves).
Equal.

*Step* $w=xa$: using the definition of $\hat\Delta$, then the induction hypothesis,
then the definition of $\Delta$, then the definition of $\hat\delta_N$:

$$
\hat\Delta(\{q_0\},xa) =\Delta\big(\hat\Delta(\{q_0\},x),a\big) \overset{\text{IH}}{=}\Delta\big(\hat\delta_N(q_0,x),a\big) =\!\!\bigcup_{p\in \hat\delta_N(q_0,x)}\!\!\delta(p,a) =\hat\delta_N(q_0,xa).
$$

This closes the induction.

**Conclusion.** Now chase the definitions:

$$
w\in L(D) \iff \hat\Delta(\{q_0\},w)\in F_D \iff \hat\Delta(\{q_0\},w)\cap F\neq\varnothing \iff \hat\delta_N(q_0,w)\cap F\neq\varnothing \iff w\in L(N),
$$

using the key lemma at the third step and the NFA acceptance definition at the
last. Hence $L(D)=L(N)$.

**The $\varepsilon$-case.** If $N$ has $\varepsilon$-moves, replace the start state
by $S_0=E(\{q_0\})$ and the transition rule by
$\Delta(S,a)=E\!\big(\bigcup_{q\in S}\delta(q,a)\big)$ — that is, take the
$\varepsilon$-closure after every step. The identical induction (now using the
$\varepsilon$-aware definition of $\hat\delta_N$) gives the same conclusion.
$\blacksquare$

> **Corollary 14.6.** DFAs and NFAs recognise **exactly the same class of
> languages.** (Every DFA is trivially an NFA; Theorem 14.5 gives the converse.)

**Remark (only reachable subsets matter).** Although $Q_D=2^{Q}$ can be huge, in
practice one builds $D$ **lazily**, generating only the subsets actually reached from
$S_0$. Often these are few. This is the standard NFA-to-DFA algorithm inside regex
tools.

### Worked subset construction

Apply the construction to the NFA $N$ of Example F (states $p_0,p_1,p_2$, no
$\varepsilon$-moves). Start from $\{p_0\}$ and compute reachable subsets:

$$
\begin{aligned} \Delta(\{p_0\},0)&=\delta(p_0,0)=\{p_0,p_1\}, & \Delta(\{p_0\},1)&=\{p_0\},\\ \Delta(\{p_0,p_1\},0)&=\{p_0,p_1\}\cup\varnothing=\{p_0,p_1\}, & \Delta(\{p_0,p_1\},1)&=\{p_0\}\cup\{p_2\}=\{p_0,p_2\},\\ \Delta(\{p_0,p_2\},0)&=\{p_0,p_1\}\cup\varnothing=\{p_0,p_1\}, & \Delta(\{p_0,p_2\},1)&=\{p_0\}\cup\varnothing=\{p_0\}. \end{aligned}
$$

Only three subsets appear. Rename $A=\{p_0\}$, $B=\{p_0,p_1\}$, $C=\{p_0,p_2\}$;
accepting subsets are those meeting $F=\{p_2\}$, namely $C$ alone.

| State | on `0` | on `1` |
|---|---|---|
| $\rightarrow\ A$ | $B$ | $A$ |
| $B$ | $B$ | $C$ |
| $\ast\ C$ | $B$ | $A$ |

**This is character-for-character the hand-built DFA of Example B.** The subset
construction *rediscovered* our suffix-tracking machine — a satisfying confirmation
that the two designs recognise the same language, "ends in `01`".

### Worked subset construction with $\varepsilon$-moves

Let $N_\varepsilon$ recognise $a^\ast b^\ast$: states $q_0$ (start), $q_1$;
$\delta(q_0,a)=\{q_0\}$, $\delta(q_0,\varepsilon)=\{q_1\}$, $\delta(q_1,b)=\{q_1\}$;
accepting $F=\{q_1\}$. First the closures: $E(\{q_0\})=\{q_0,q_1\}$ and
$E(\{q_1\})=\{q_1\}$.

Start $S_0=E(\{q_0\})=\{q_0,q_1\}=:A$ (accepting — contains $q_1$).

$$
\begin{aligned} \Delta(A,a)&=E(\delta(q_0,a)\cup\delta(q_1,a))=E(\{q_0\})=\{q_0,q_1\}=A,\\ \Delta(A,b)&=E(\delta(q_0,b)\cup\delta(q_1,b))=E(\{q_1\})=\{q_1\}=:B,\\ \Delta(B,a)&=E(\delta(q_1,a))=E(\varnothing)=\varnothing=:\varnothing,\\ \Delta(B,b)&=E(\{q_1\})=\{q_1\}=B, \end{aligned}
$$

and the empty set is an absorbing non-accepting dead state.

| State | on `a` | on `b` |
|---|---|---|
| $\rightarrow\ \ast\ A$ | $A$ | $B$ |
| $\ast\ B$ | $\varnothing$ | $B$ |
| $\varnothing$ | $\varnothing$ | $\varnothing$ |

**Traces.** `aab`: $A\to A\to A\to B$ accept ($aab=a^2b^1$). `aba`:
$A\to A\to B\to\varnothing$ reject (`aba` is not of the form $a^\ast b^\ast$). `ba`:
$A\to B\to\varnothing$ reject. All correct.

---

## 14.9 Regular expressions and Kleene's theorem

We have two automaton-based definitions of "regular" (DFA and NFA, now known equal).
There is a third, purely syntactic one.

> **Definition (regular expression).** The **regular expressions** over $\Sigma$, and
> the language $L(R)$ each denotes, are defined by recursion:
> - $\varnothing$ is a regex with $L(\varnothing)=\varnothing$;
> - $\varepsilon$ is a regex with $L(\varepsilon)=\{\varepsilon\}$;
> - each $a\in\Sigma$ is a regex with $L(a)=\{a\}$;
> - if $R,S$ are regexes, so are $(R+S)$, $(RS)$, and $(R^\ast)$, with
>

$$
L(R+S)=L(R)\cup L(S),\quad L(RS)=L(R)L(S),\quad L(R^\ast)=L(R)^\ast.
$$

>
> Binding tightest to loosest: $^\ast$, then concatenation, then $+$. So
> $ab^\ast+c$ means $\big(a(b^\ast)\big)+c$.

For instance $(0+1)^\ast 01$ denotes "ends in `01`"; $(0+1)^\ast 001 (0+1)^\ast$
denotes "contains `001`"; $0^\ast 1^\ast$ denotes $a^\ast b^\ast$ (with $0,1$ for
$a,b$). These are the same languages we built machines for.

> **Theorem 14.7 (Kleene, 1956 — stated).** A language is regular (recognised by
> some DFA/NFA) **if and only if** it is denoted by some regular expression.

We do not give the full two-way proof, but the forward-hard direction is short and
ties the chapter together, so we sketch it; the converse is noted.

*Regex $\to$ NFA (Thompson's construction, sketch).* Build an $\varepsilon$-NFA by
recursion on the regex, maintaining the invariant "one start state, one accepting
state." Base cases $\varnothing,\varepsilon,a$ are one- or two-state machines. For
$R+S$, add a new start with $\varepsilon$-edges into the two sub-machines' starts and
a new accept with $\varepsilon$-edges from their accepts. For $RS$, glue $R$'s accept
to $S$'s start with an $\varepsilon$-edge. For $R^\ast$, add a new start/accept state
with $\varepsilon$-edges to $R$'s start, from $R$'s accept back to $R$'s start, and
straight through for the empty string. Each rule adds $O(1)$ states, so the NFA has
size linear in the regex; by the subset construction (Theorem 14.5) it converts to a
DFA. This is exactly how regex libraries compile a pattern.

*NFA $\to$ regex (converse, noted).* Eliminate states one at a time from the
automaton, relabelling the remaining edges with regexes that account for the removed
state's paths (the **state-elimination** / GNFA method), until a single edge labelled
by the answer regex remains. $\square$

> **Definition (regular language — final form).** By Corollary 14.6 and Theorem 14.7,
> the following are **the same class of languages**, the **regular languages**:
> those recognised by a DFA; by an NFA; and those denoted by a regular expression.
> "Finite automaton", "regular language", "regular expression" are three views of one
> idea — *the languages a finite-memory machine can recognise.*

---

## 14.10 Closure properties of the regular languages

The regular languages are remarkably robust: combine them with the natural set and
string operations and you stay regular. These closure theorems are workhorses — both
for building machines compositionally and (via §14.11) for proving *non*-regularity.
Note how they mirror the logical connectives of Lecture 6: union is "or",
intersection is "and", complement is "not".

> **Theorem 14.8 (closure under complement).** If $L$ is regular over $\Sigma$, so is
> $\overline{L}=\Sigma^\ast\setminus L$.

*Proof.* Take a **DFA** $M=(Q,\Sigma,\delta,q_0,F)$ with $L(M)=L$ — crucially a DFA,
whose $\delta$ is total, so every string has a run ending in a well-defined state.
Form $M'=(Q,\Sigma,\delta,q_0,Q\setminus F)$ by swapping accepting and
non-accepting states. Since the run of a string is identical in $M$ and $M'$, for
every $w$,

$$
w\in L(M') \iff \hat\delta(q_0,w)\in Q\setminus F \iff \hat\delta(q_0,w)\notin F \iff w\notin L(M).
$$

Hence $L(M')=\overline{L}$. $\blacksquare$

**Common pitfall.** This works only for a **complete DFA**. Swapping the accepting
set of an **NFA** does *not* complement its language (because "some path accepts" and
"some path rejects" can both hold at once). Determinise first, ensure $\delta$ is
total, *then* swap.

> **Theorem 14.9 (product construction: closure under intersection and union).** If
> $L_1,L_2$ are regular, so are $L_1\cap L_2$ and $L_1\cup L_2$.

*Proof.* Let $M_i=(Q_i,\Sigma,\delta_i,q_{0,i},F_i)$ be DFAs with $L(M_i)=L_i$. Run
both **in parallel** on one input by taking states to be *pairs*:

$$
M=\big(Q_1\times Q_2,\ \Sigma,\ \delta,\ (q_{0,1},q_{0,2}),\ F\big),\qquad \delta\big((p,q),a\big)=\big(\delta_1(p,a),\,\delta_2(q,a)\big).
$$

Choose $F=F_1\times F_2$ for **intersection**, or
$F=\{(p,q):p\in F_1\text{ or }q\in F_2\}$ for **union**.

*Parallel-run lemma.* $\hat\delta\big((p,q),w\big)=\big(\hat\delta_1(p,w),\, \hat\delta_2(q,w)\big)$ for all $w$. Induct on $|w|$: base $w=\varepsilon$ gives
$(p,q)$ on both sides; step $w=xa$,

$$
\hat\delta((p,q),xa)=\delta\big(\hat\delta((p,q),x),a\big) \overset{\text{IH}}{=}\delta\big((\hat\delta_1(p,x),\hat\delta_2(q,x)),a\big) =\big(\hat\delta_1(p,xa),\hat\delta_2(q,xa)\big).
$$

Now for intersection, $w\in L(M)$ iff
$\big(\hat\delta_1(q_{0,1},w),\hat\delta_2(q_{0,2},w)\big)\in F_1\times F_2$ iff
$\hat\delta_1(q_{0,1},w)\in F_1$ **and** $\hat\delta_2(q_{0,2},w)\in F_2$ iff
$w\in L_1\cap L_2$. The union case is identical with "and" replaced by "or".
$\blacksquare$

**Worked use.** To accept binary strings with an **even number of $0$s AND an odd
number of $1$s**, take the product of the two 2-state parity DFAs: $2\times2=4$
states $\{(\text{e}_0,\text{e}_1),(\text{e}_0,\text{o}_1),(\text{o}_0,\text{e}_1), (\text{o}_0,\text{o}_1)\}$, start $(\text{e}_0,\text{e}_1)$, accepting the single
state $(\text{e}_0,\text{o}_1)$.

> **Theorem 14.10 (closure under union, concatenation, star).** If $L_1,L_2$ are
> regular, so are $L_1\cup L_2$, $L_1L_2$, and $L_1^\ast$.

*Proof (via NFAs).* Take NFAs $N_1,N_2$ for $L_1,L_2$ and use the Thompson gadgets of
§14.9. **Union:** a new start with $\varepsilon$-edges into both starts. **Concatenation:**
$\varepsilon$-edges from $N_1$'s accepting states to $N_2$'s start; start $=N_1$'s
start, accept $=N_2$'s accepts. **Star:** a new start/accept state with an
$\varepsilon$-edge to $N_1$'s start, $\varepsilon$-edges from $N_1$'s accepts back to
its start, and acceptance of $\varepsilon$ built in. In each case one checks the
$\varepsilon$-NFA accepts exactly the intended language; the subset construction then
yields a DFA. (These three operations are precisely the constructors of regular
expressions — this theorem is the "$\Leftarrow$" of Kleene's theorem in disguise.)
$\blacksquare$

> **Corollary 14.11 (closure under set difference).** If $L_1,L_2$ are regular, so is
> $L_1\setminus L_2=L_1\cap\overline{L_2}$ — a regular language by Theorems 14.8 and
> 14.9.

**Remark (closure as a proof tool).** Closure runs *backwards* too. If we already
know some language $K$ is **not** regular, and we can *manufacture* $K$ from a
suspect language $L$ using operations that preserve regularity, then $L$ cannot be
regular either — otherwise $K$ would be. We exploit exactly this in §14.11.

---

## 14.11 The limits of finite memory: the pumping lemma

Everything so far *builds* regular languages. We now prove that some languages are
**not** regular — that finite memory is a genuine limitation. The tool is the
**pumping lemma**, whose engine is the pigeonhole principle (Lecture 8): a run
longer than the number of states must repeat a state, and a repeated state is a loop
we can traverse any number of times.

![Pumping lemma: a long accepted string splits as x·y·z where the middle y is a loop that can be repeated, so xyⁱz is accepted for every i](img/l14_pumping.png)

> **Theorem 14.12 (pumping lemma for regular languages).** If $L$ is regular, then
> there is a constant $p\ge 1$ (a **pumping length**) such that **every** string
> $s\in L$ with $|s|\ge p$ can be split as $s=xyz$ with
> 1. $|y|\ge 1$ (the middle part is non-empty),
> 2. $|xy|\le p$ (the loop occurs within the first $p$ symbols), and
> 3. $xy^{\,i}z\in L$ for **all** $i\ge 0$ (the middle part may be "pumped").

*Proof.* Since $L$ is regular, fix a DFA $M=(Q,\Sigma,\delta,q_0,F)$ with $L(M)=L$,
and set $p=|Q|$, the number of states. Let $s=a_1a_2\cdots a_n\in L$ with
$n=|s|\ge p$. Consider the run

$$
r_0,r_1,\dots,r_n,\qquad r_0=q_0,\quad r_i=\hat\delta(q_0,a_1\cdots a_i).
$$

Look at the first $p+1$ of these states, $r_0,r_1,\dots,r_p$. They are $p+1$ states
drawn from a set of only $p$ states, so by the **pigeonhole principle** two of them
coincide: there exist indices $j<k$ with $0\le j<k\le p$ and $r_j=r_k$.

Define the split

$$
x=a_1\cdots a_j,\qquad y=a_{j+1}\cdots a_k,\qquad z=a_{k+1}\cdots a_n.
$$

Then $|y|=k-j\ge 1$ (condition 1) and $|xy|=k\le p$ (condition 2). Reading $y$ from
state $r_j$ returns to $r_k=r_j$, so $\hat\delta(r_j,y)=r_j$ — a **loop**. By Lemma
14.1 (concatenation law) and induction on $i$, $\hat\delta(r_j,y^{\,i})=r_j$ for
every $i\ge 0$: going around the loop any number of times lands back at $r_j$.
Therefore, again by Lemma 14.1,

$$
\hat\delta(q_0,\,xy^{\,i}z) =\hat\delta\big(\hat\delta(\hat\delta(q_0,x),\,y^{\,i}),\,z\big) =\hat\delta\big(\hat\delta(r_j,y^{\,i}),\,z\big) =\hat\delta(r_j,z) =\hat\delta(r_k,z)=r_n .
$$

Since $s=xyz\in L$, we have $r_n\in F$; hence $\hat\delta(q_0,xy^{\,i}z)=r_n\in F$,
i.e. $xy^{\,i}z\in L$ for all $i\ge 0$ (condition 3). $\blacksquare$

**How to *use* it (the adversary game).** The lemma is a one-directional implication:
regular $\Rightarrow$ pumpable. To prove a language $L$ is **not** regular we use the
contrapositive as a game against an adversary:

1. *(Adversary)* Suppose $L$ were regular; it hands you some pumping length $p$
   (you do **not** get to choose $p$).
2. *(You)* Choose a specific string $s\in L$ with $|s|\ge p$, cleverly, usually in
   terms of $p$.
3. *(Adversary)* Splits $s=xyz$ subject only to $|y|\ge1$ and $|xy|\le p$ (you must
   handle **every** legal split).
4. *(You)* Exhibit one $i\ge0$ with $xy^{\,i}z\notin L$. That contradicts the lemma,
   so $L$ is not regular.

### Worked non-regularity proof: $\{0^n1^n\}$

> **Theorem 14.13.** $L=\{0^n1^n : n\ge 0\}$ is **not** regular.

*Proof.* Suppose, for contradiction, that $L$ is regular, and let $p$ be a pumping
length from Theorem 14.12. Choose

$$
s=0^{p}1^{p}\in L,\qquad |s|=2p\ge p.
$$

By the pumping lemma $s=xyz$ with $|y|\ge1$ and $|xy|\le p$. Because the first $p$
symbols of $s$ are **all $0$s**, the prefix $xy$ (of length $\le p$) consists solely
of $0$s; in particular $y=0^{m}$ for some $m\ge 1$. Pump with $i=2$:

$$
xy^{2}z=0^{\,p+m}1^{\,p}.
$$

Since $m\ge1$ this string has more $0$s than $1$s, so it is **not** of the form
$0^n1^n$ and $xy^2z\notin L$ — contradicting condition 3. Therefore $L$ is not
regular. $\blacksquare$

**Intuition.** $L$ demands matching an unbounded count of $0$s against an equal count
of $1$s. A finite automaton has only $p=|Q|$ states, so after reading enough $0$s it
must reuse a state and thereby "forget" exactly how many it has seen. The pumping
lemma turns that forgetting into a concrete counterexample.

### A second worked proof: perfect squares of $0$s

> **Theorem 14.14.** $L=\{0^{\,n^2} : n\ge 0\}$ (strings of $0$s whose length is a
> perfect square) is **not** regular.

*Proof.* Suppose $L$ is regular with pumping length $p$. Choose $s=0^{\,p^2}\in L$
(note $|s|=p^2\ge p$ since $p\ge1$). Write $s=xyz$ with $1\le|y|\le|xy|\le p$; say
$|y|=m$, so $1\le m\le p$. Pump to $i=2$: the string $xy^2z=0^{\,p^2+m}$ has length
$p^2+m$. Now

$$
p^2 < p^2+m \le p^2+p < p^2+2p+1=(p+1)^2.
$$

So $p^2+m$ lies **strictly between the consecutive squares** $p^2$ and $(p+1)^2$ and
is therefore not a perfect square; hence $xy^2z\notin L$, a contradiction. Thus $L$
is not regular. $\blacksquare$

**Remark (pairing with closure — equal $0$s and $1$s).** Let
$E=\{w\in\{0,1\}^\ast : \#_0(w)=\#_1(w)\}$. Is $E$ regular? Suppose it were. The
language $0^\ast1^\ast$ *is* regular (regex $0^\ast1^\ast$), so by closure under
intersection (Theorem 14.9) $E\cap L(0^\ast1^\ast)$ would be regular. But

$$
E\cap L(0^\ast1^\ast)=\{0^n1^n:n\ge0\},
$$

which is **not** regular (Theorem 14.13) — contradiction. Hence $E$ is not regular.
This is the "closure as a proof tool" remark of §14.10 in action: we avoided a fresh
pumping argument by *reducing* to one we already had.

**Common pitfall.** (a) You do **not** choose $p$; you must survive whatever $p$ the
adversary picks. (b) You do **not** choose the split $x,y,z$; you must defeat *every*
split obeying $|y|\ge1,\ |xy|\le p$. Choosing $s=0^p1^p$ (rather than, say, $0^p1$)
is what *forces* $y$ into the $0$-block via $|xy|\le p$. (c&#41; The lemma is **not** an
"if and only if": some non-regular languages happen to be pumpable, so a *successful*
pump does not prove regularity. Use the lemma only to prove non-regularity.

---

## 14.12 Beyond finite automata (a signpost)

A finite automaton is the **weakest** standard abstract machine: its only memory is
its state. The languages just shown non-regular are not exotic — they are the
bread-and-butter of programming languages (balanced brackets, $a^nb^n$-style
matching). To recognise them we must *add memory* to the same tape-reader-control
picture of §14.3:

- Add a **stack** (last-in-first-out memory) and you get a **pushdown automaton**,
  which recognises the **context-free languages** — enough for $\{0^n1^n\}$, balanced
  parentheses, and the grammars of programming languages.
- Add an **unbounded read/write tape** and you get a **Turing machine**, the most
  general model of computation, recognising the **recursively enumerable** languages.

These sit at higher rungs of the **Chomsky hierarchy** (regular $\subsetneq$
context-free $\subsetneq$ context-sensitive $\subsetneq$ recursively enumerable) and
are the subject of a full course in the theory of computation. They lie beyond this
introduction; we mention them only to place finite automata on the map. Likewise the
**DFA-minimisation** algorithm (there is a unique smallest DFA per regular language,
computable by merging indistinguishable states — the algorithmic face of
Myhill–Nerode) is noted but not developed here.

![The Chomsky hierarchy as nested language classes: regular (finite memory) ⊊ context-free ⊊ context-sensitive ⊊ recursively enumerable](img/l14_hierarchy.png)

---

## Historical note

The finite-state idea was first written down by **Warren McCulloch** and **Walter
Pitts** in 1943, who modelled networks of idealised neurons as devices with a finite
number of states. **Stephen Cole Kleene**, analysing those nerve nets in a 1951 RAND
memorandum published in the 1956 volume *Automata Studies*, introduced **regular
events** (our regular expressions) and proved the equivalence now called **Kleene's
theorem** (Theorem 14.7). The output-producing machines are named for their
inventors at Bell Labs: **George H. Mealy** ("A Method for Synthesizing Sequential
Circuits", 1955) attached output to transitions, while **Edward F. Moore**
("Gedanken-experiments on Sequential Machines", 1956) attached it to states.
**Michael O. Rabin** and **Dana Scott** introduced nondeterministic automata and the
subset construction (Theorem 14.5) in their 1959 paper "Finite Automata and Their
Decision Problems", work for which they shared the 1976 Turing Award. The pumping
lemma and the algebraic characterisation of regularity (**Myhill–Nerode**) followed
in the late 1950s. It is a striking feature of the subject that a single, small
abstraction — the finite automaton — was reached almost simultaneously from
neuroscience, logic, and circuit engineering.

---

## CS connections

Finite automata are not a museum piece; they run inside tools you use daily.

- **Lexical analysis (lexers).** The first phase of every compiler chops source code
  into tokens (identifiers, numbers, operators). Each token class is described by a
  regular expression; a tool like **lex/flex** compiles the union of them (via
  Thompson's construction and the subset construction) into a single DFA that scans
  the source in linear time. This is §14.8–14.9 turned into a product.
- **Regular-expression engines.** `grep`, RE2, and lexer generators simulate an NFA
  or its determinised DFA. Ken Thompson's 1968 `grep` used exactly the on-the-fly NFA
  simulation of §14.7; guaranteed-linear engines (RE2) determinise lazily as in the
  remark after Theorem 14.5, avoiding the exponential blow-up that "backtracking"
  regex engines suffer.
- **Network protocols.** TCP connection management is specified as a finite-state
  machine (states `LISTEN`, `SYN-SENT`, `ESTABLISHED`, `TIME-WAIT`, …); the
  transitions are triggered by packets and timeouts — a Mealy/Moore machine in
  production.
- **Digital hardware.** Controllers, vending machines, and traffic lights are
  synthesised directly from Mealy/Moore descriptions (§14.6) into flip-flops plus
  combinational logic (§14.1) — closing the loop back to Lecture 5.
- **String search and validation.** The Knuth–Morris–Pratt matcher is essentially the
  substring-DFA of Example C; input validation for dates, phone numbers, and URLs is
  DFA membership testing.

---

## Chapter summary

- **Combinational vs sequential.** Combinational logic (Lecture 5) computes a fixed
  Boolean function of the current inputs (adders, decoders, ALU); **sequential** logic
  adds **state**, held in **flip-flops** ($k$ flip-flops $\Rightarrow 2^k$ states),
  so output can depend on the past. State is exactly what automata theory formalises.
- **Vocabulary.** An alphabet $\Sigma$, strings $\Sigma^\ast$ under concatenation
  (a monoid with unit $\varepsilon$), and **languages** $L\subseteq\Sigma^\ast$;
  distinguish $\varepsilon$, $\varnothing$, and $\{\varepsilon\}$.
- **DFA** $M=(Q,\Sigma,\delta,q_0,F)$ with total $\delta:Q\times\Sigma\to Q$; the
  extended $\hat\delta$ satisfies the concatenation law (Lemma 14.1); $M$ **accepts**
  $w$ iff $\hat\delta(q_0,w)\in F$, and $L(M)=\{w:\hat\delta(q_0,w)\in F\}$. Design =
  pick states recording just-enough finite information (parity, running remainder,
  suffix progress); always total (add a **dead state**).
- **Mealy vs Moore** transducers attach output to transitions vs states; they are
  interconvertible and model sequential circuits exactly.
- **NFA** allows set-valued transitions and $\varepsilon$-moves; it accepts if **some**
  path succeeds. The **subset construction** (Theorem 14.5) determinises any NFA, so
  DFAs and NFAs recognise the **same** class — but NFAs can be exponentially smaller.
- **Regular languages** = DFA-recognisable = NFA-recognisable = **regular-expression**
  denotable (**Kleene**, Theorem 14.7). The class is **closed** under union,
  intersection (**product construction**, Theorem 14.9), complement (swap accepting
  states of a *DFA*, Theorem 14.8), concatenation, and Kleene star (Theorem 14.10).
- **Pumping lemma** (Theorem 14.12): long strings in a regular language contain a
  pumpable loop. Its contrapositive proves **non-regularity**: $\{0^n1^n\}$,
  $\{0^{n^2}\}$, and equal-count languages are **not** regular (Theorems
  14.13–14.14) — finite memory has real limits.
- **Beyond:** adding a stack gives pushdown automata (context-free); an unbounded tape
  gives Turing machines. Minimisation (Myhill–Nerode) is noted, not developed.

---

## Exercises

### Warm-up

**1.** Let $\Sigma=\{a,b\}$. List all strings of length $\le 2$ over $\Sigma$, and
give $|\varepsilon|$, $|abba|$, and the string $(ab)^3$. Explain why
$\varnothing\ne\{\varepsilon\}$.

**2.** For the even-number-of-$1$s DFA (Example A), trace the runs on `11010` and on
`010`, and state whether each is accepted.

**3.** Write out the five components of the DFA tuple $M=(Q,\Sigma,\delta,q_0,F)$ and
say how each corresponds to the Mealy/Moore transducer tuple $M=(S,I,O,f,g,s_0,F)$ of
§14.6 — and which two components a transducer adds.

**4.** For the "ends in `01`" DFA (Example B), trace `1101` and `0010` and give the
verdicts.

**5.** For the running-parity transducer (§14.6), write the full **Moore** and
**Mealy** output strings on input `0110`, and explain why they differ in length by
exactly one.

**6.** Give a regular expression for each: (a) strings over $\{0,1\}$ that begin with
`1`; (b) strings that end in `01`; (c&#41; strings that contain `001`.

### Standard

**7.** Design a DFA (states, transition table, start, accepting set) over $\{0,1\}$
for strings whose number of $0$s is **divisible by $3$**. Trace it on `00100`.

**8.** Design a DFA over $\{0,1\}$ for "**does not contain** `11`" (no two consecutive
$1$s). Then, using Theorem 14.8, describe how to obtain a DFA for the complement
("contains `11`").

**9.** Use the **product construction** (Theorem 14.9) to build a DFA for "even number
of $0$s **and** odd number of $1$s". Give its four states, start, and accepting set,
and trace `0110`.

**10.** Apply the **subset construction** to the NFA $N$ with states $\{p_0,p_1,p_2\}$,
start $p_0$, accepting $p_2$, and
$\delta(p_0,0)=\{p_0,p_1\}$, $\delta(p_0,1)=\{p_0\}$, $\delta(p_1,1)=\{p_2\}$ (all
other entries $\varnothing$). List the reachable DFA states and give its table. Which
familiar language is this?

**11.** Give a Mealy machine over input $\{0,1\}$, output $\{0,1\}$, that outputs `1`
on exactly the step whose input symbol completes an occurrence of the pattern `01`
(and `0` otherwise). Trace it on `10011`.

**12.** For the divisible-by-$3$ DFA (Example D), trace `1110` and `10010` and give
the values and verdicts. Confirm against ordinary arithmetic.

**13.** Prove that the class of regular languages is closed under **set difference**
$L_1\setminus L_2$, citing the theorems you use.

### Challenge

**14.** Prove that $L=\{a^nb^m : n>m\ge 0\}$ is **not** regular. (Hint: pick
$s=a^{p+1}b^{p}$ and pump *down*.)

**15.** Prove that the language of **binary palindromes** $\{w\in\{0,1\}^\ast : w=w^{R}\}$ is not regular, where $w^{R}$ is $w$ reversed. (Hint: try
$s=0^{p}1\,0^{p}$.)

**16.** Prove the regular languages are closed under **reversal**: if $L$ is regular
then $L^{R}=\{w^{R}:w\in L\}$ is regular. (Hint: reverse every edge of an NFA for
$L$, swap start and accept roles using an $\varepsilon$-move.)

**17.** Show that any DFA recognising $L_k=\{w:$ the $k$-th symbol from the end is
`1`$\}$ needs at least $2^k$ states. (Hint: exhibit $2^k$ length-$k$ strings that are
pairwise **distinguishable** — for each pair, a suffix that one can complete into $L_k$
and the other cannot — and argue they must reach distinct states.)

**18.** A DFA has $p$ states and accepts **at least one** string. Prove it accepts a
string of length $<p$. (Hint: a shortest accepted string cannot repeat a state, by the
pumping argument.) Conclude an algorithm to test whether $L(M)=\varnothing$.

**19.** Prove the pumping lemma's index bound is tight in the following sense: give a
regular language and a string in it for which pumping with $i=0$ (deleting $y$) leaves
the language, illustrating that condition 3 must hold for *all* $i\ge0$, including
$i=0$.

**20.** Using closure properties only (no direct pumping), prove that
$\{0^n1^m : n\ne m\}$ is not regular. (Hint: complement, intersect with $0^\ast1^\ast$,
and use Theorem 14.13.)

---

## Selected answers & hints

**2.** `11010`: $q_{\text{e}}\to q_{\text{o}}\to q_{\text{e}}\to q_{\text{e}}\to q_{\text{o}}\to q_{\text{o}}$; ends in $q_{\text{o}}$ — **rejected** (three $1$s,
odd). `010`: $q_{\text{e}}\to q_{\text{e}}\to q_{\text{o}}\to q_{\text{o}}$; ends in
$q_{\text{o}}$ — **rejected** (one $1$, odd).

**5.** The running parity of $1$s after reading $\varepsilon,0,01,011,0110$ is
$0,0,1,0,0$. Moore output on `0110` is `00100` (5 symbols: it visits states
$E,E,O,E,E$ and prints their labels $0,0,1,0,0$); Mealy output is `0100` (4 symbols:
one per transition, $0,1,0,0$). Moore emits one symbol per *state visited* — there
are $n+1=5$ states for an input of length $n=4$, including the pre-input output —
while Mealy emits one symbol per *transition*, exactly $n=4$. Hence the length
differs by one, and Moore's string is Mealy's with the initial `0` prepended.

**6.** (a) $1(0+1)^\ast$; (b) $(0+1)^\ast 01$; (c&#41; $(0+1)^\ast 001(0+1)^\ast$.

**7.** States $t_0,t_1,t_2$ = (number of $0$s) $\bmod\,3$; reading `1` is a self-loop
on every state, reading `0` cycles $t_0\to t_1\to t_2\to t_0$; start and only
accepting state $t_0$. On `00100`: $t_0\to t_1\to t_2\to t_2\to t_0\to t_1$; ends
$t_1$ — **rejected** (four $0$s, $4\bmod3=1$).

**9.** States are pairs (parity of $0$s, parity of $1$s):
$(\text{e},\text{e}),(\text{e},\text{o}),(\text{o},\text{e}),(\text{o},\text{o})$;
start $(\text{e},\text{e})$; accepting the single state $(\text{e},\text{o})$. On
`0110`: $(\text{e},\text{e})\xrightarrow{0}(\text{o},\text{e})\xrightarrow{1} (\text{o},\text{o})\xrightarrow{1}(\text{o},\text{e})\xrightarrow{0}(\text{e},\text{e})$;
ends $(\text{e},\text{e})\ne(\text{e},\text{o})$ — **rejected** (two $0$s even, two
$1$s even, so $1$s not odd).

**10.** Reachable states $A=\{p_0\},B=\{p_0,p_1\},C=\{p_0,p_2\}$ with the table
$A\xrightarrow{0}B,\ A\xrightarrow{1}A,\ B\xrightarrow{0}B,\ B\xrightarrow{1}C,\ C\xrightarrow{0}B,\ C\xrightarrow{1}A$, accepting $C$ — the language "**ends in
`01`**" (identical to Example B), confirming Theorem 14.5.

**11.** Reuse Example B's states $A,B,C$ as a Mealy machine: on every transition
*into* $C$ (namely $B\xrightarrow{1}$) output `1`, otherwise `0`. On `10011`:
transitions $A\xrightarrow{1}A/0,\ A\xrightarrow{0}B/0,\ B\xrightarrow{0}B/0,\ B\xrightarrow{1}C/1,\ C\xrightarrow{1}A/0$ — output `00010`.

**13.** $L_1\setminus L_2=L_1\cap\overline{L_2}$. $\overline{L_2}$ is regular by
complement closure (Theorem 14.8), and the intersection of two regular languages is
regular by the product construction (Theorem 14.9); hence $L_1\setminus L_2$ is
regular.

**14.** Adversary gives $p$. Choose $s=a^{p+1}b^{p}\in L$ ($|s|=2p+1\ge p$). Since
$|xy|\le p$, $y$ lies in the $a$-block, $y=a^{m}$, $m\ge1$. Pump **down** ($i=0$):
$xy^0z=a^{\,p+1-m}b^{\,p}$. As $m\ge1$, the number of $a$'s is $p+1-m\le p$, which is
**not** $>p$, so $xy^0z\notin L$ — contradiction.

**16.** From an NFA $N=(Q,\Sigma,\delta,q_0,F)$ for $L$, build $N^R$: reverse the
direction of every transition, make the old accepting states into (nondeterministic)
starts — add a fresh start $s$ with $\varepsilon$-edges to each old accept — and make
$q_0$ the sole accepting state. A path spelling $w$ from $q_0$ to $F$ in $N$ becomes a
path spelling $w^R$ from $s$ to $q_0$ in $N^R$, so $L(N^R)=L^{R}$; determinise if a
DFA is wanted.

**18.** Let $w$ be a **shortest** accepted string and suppose $|w|\ge p=|Q|$. By the
pumping lemma $w=xyz$ with $|y|\ge1$ and $xy^0z=xz\in L$, but $|xz|<|w|$ — contradicting
minimality. Hence the shortest accepted string has length $<p$. Algorithm: test all
strings of length $<p$ (or, better, check by graph reachability whether any accepting
state is reachable from $q_0$); $L(M)=\varnothing$ iff none is accepted.

**20.** If $\{0^n1^m:n\ne m\}$ were regular, so would be its complement, and
intersecting the complement with the regular language $L(0^\ast1^\ast)$ gives exactly
$\{0^n1^n:n\ge0\}$ — non-regular by Theorem 14.13. Contradiction, so
$\{0^n1^m:n\ne m\}$ is not regular.

---

## Further reading

- Michael Sipser, *Introduction to the Theory of Computation* — Chapter 1 (regular
  languages, DFAs/NFAs, the subset construction, regular expressions, and the pumping
  lemma) is the closest match to this chapter.
- John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, *Introduction to Automata Theory,
  Languages, and Computation* — a fuller treatment, including minimisation and the
  Myhill–Nerode theorem.
- Kenneth Rosen, *Discrete Mathematics and Its Applications* — the chapter on modelling
  computation gives a gentler, discrete-math-oriented introduction consistent with this
  course.

## Self-check questions

1. State precisely the difference between combinational and sequential logic, and
   explain why a two-bit counter cannot be built from combinational gates alone.
2. Give the five components of $M=(Q,\Sigma,\delta,q_0,F)$ and define $\hat\delta$ by
   recursion. Why must $\delta$ be **total**?
3. Prove that the DFA of Example A recognises exactly the even-$\#_1$ strings.
4. What does the subset construction show, and why does swapping the accepting set of
   an **NFA** fail to complement its language?
5. State the pumping lemma and use it to prove $\{0^n1^n\}$ is not regular.
6. Name the three equivalent characterisations of the regular languages, and list the
   operations under which the class is closed.