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.

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 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.

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

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).

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.

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$.

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.

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).

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

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):

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 $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.

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.

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.

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$.