Theory of Computation: Lecture 2

From Concatenation to Nondeterminism

Complement, union, and intersection all came with DFA constructions. Concatenation did not: to recognize $L_1\circ L_2$, a machine reading $w=xy$ must know where the first part $x$ ends and the second part $y$ begins, and the input does not mark that split. A deterministic run cannot try all splits, so the machine is given a new ability: it may guess.

Nondeterminism. A machine is nondeterministic when it may have several possible next moves. A string is accepted when at least one possible computation accepts; all other computations are simply ignored.

Nondeterministic Finite Automata

Nondeterministic finite automaton (NFA). A finite automaton whose transition rule may offer any number of next states, including none, and may move without reading input. The differences from a DFA:

• Branching. On a given state and symbol, there may be more than one next state.
• Missing transition. There may be no next state at all; that computation branch dies.
• Epsilon transition. A transition labeled $\epsilon$ moves to another state without consuming an input symbol.

Example 1. Strings containing 11 or 101.

This NFA waits in $q_1$ until it guesses that a matching substring has started. If the guess succeeds, it reaches $q_4$ and stays there.

$$L(N)=\{w\in\{0,1\}^*\mid w\text{ contains }11\text{ or }101\}$$

The transition $q_2\to q_3$ has two labels. Reading 0 helps match 101; taking $\epsilon$ helps match 11.

Accepted: $11$, $101$, $010110$. Rejected: $\epsilon$, $0$, $1000$.

Formal NFA. An NFA is a 5-tuple with the same parts as a DFA except for the transition function:

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

Symbol	Role
$Q$	states
$\Sigma$	alphabet
$\delta:Q\times(\Sigma\cup\{\epsilon\})\to 2^Q$	transition function
$q_0\in Q$	start state
$F\subseteq Q$	accepting states

Power set. The power set $2^Q$ is the set of all subsets of $Q$. The transition function returns an element of $2^Q$ because there may be zero, one, or many next states.

If $Q=\{q_1,q_2\}$, then $2^Q=\{\varnothing,\{q_1\},\{q_2\},\{q_1,q_2\}\}$.

For Example 1, the diagram is equivalent to this transition table, where each cell is a set and an impossible move is $\varnothing$, not an error:

State	0	1	$\epsilon$
$q_1$	$\{q_1\}$	$\{q_1,q_2\}$	$\varnothing$
$q_2$	$\{q_3\}$	$\varnothing$	$\{q_3\}$
$q_3$	$\varnothing$	$\{q_4\}$	$\varnothing$
$q_4$	$\{q_4\}$	$\{q_4\}$	$\varnothing$

NFA acceptance. An NFA accepts $w$ if there exists a path that starts at $q_0$, reads exactly $w$, and ends in a state of $F$ when the input ends. Epsilon transitions may be taken anywhere along the path because they read nothing. Visiting an accepting state in the middle of the input proves nothing; only the state where the input runs out counts.

Computation of an NFA. Two equivalent ways to read the same definition.

• Parallel view. The machine forks into one copy per possible move and runs all copies at once. A copy with no valid move dies. The input is accepted if any surviving copy ends in an accepting state.
• Guess view. The machine magically guesses a single lucky path and accepts if that path ends in an accepting state.

Guess and verify: design an NFA so that a guess marks the interesting position, and the rest of the machine merely checks it.

Example 2. Every possibility at once on 010110.

Running Example 1's NFA in the parallel view, the set of live states after each symbol (including states reached by free $\epsilon$-moves) evolves as follows.

Input read	Possible states
start	$\{q_1\}$
0	$\{q_1\}$
1	$\{q_1,q_2,q_3\}$
0	$\{q_1,q_3\}$
1	$\{q_1,q_2,q_3,q_4\}$
1	$\{q_1,q_2,q_3,q_4\}$
0	$\{q_1,q_3,q_4\}$

Reading 1 in $q_1$ opens three branches: stay in $q_1$, move to $q_2$, or move to $q_2$ and slide on to $q_3$ by the $\epsilon$-transition. Branches die quietly, as $q_3$ does on 0. The final set contains the accepting state $q_4$, so 010110 is accepted: in the guess view, one lucky path guessed the 101 in the middle.

Designing NFAs

Nondeterminism has no physical analog, yet it earns its place: NFAs are often easier to build and much smaller than DFAs for the same language, and the equivalence theorem below converts any NFA into a DFA mechanically. Two patterns cover most designs.

Guess-and-check pattern. The NFA stays in a broad waiting state, guesses the important position, then checks the remaining symbols.

Example 3. A 1 in the third position from the end.

The machine may leave $q_1$ whenever it reads a 1. After that guess, exactly two more symbols must be read before the input ends.

$$L=\{w\in\{0,1\}^*\mid w\text{ has }1\text{ in the third position from the end}\}$$

The accepting state has no outgoing transition, so a branch that guesses too early dies before the input ends. The string $1000$ visits $q_4$ after three symbols but is rejected: the path is not at $q_4$ when the input ends.

Accepted: $100$, $000100$, $11011$. Rejected: $11$, $0011$, $1000$.

Epsilon-branching pattern. An NFA can choose between several submachines before reading any input, which is exactly a union of their languages.

Example 4. Unary strings whose length is divisible by 2 or 3.

The start state chooses, by $\epsilon$-transition, whether to test divisibility by 2 or divisibility by 3.

The Subset Construction

The parallel view already contains the determinization idea. In Example 2, the set of possible states after each prefix evolved deterministically: each row of the table was computed from the previous row and one input symbol, with no guessing anywhere. A DFA can therefore simulate an NFA by storing that whole set as its own single state.

Possible-states set. After reading a prefix, the set of all NFA states reachable by some path reading that prefix. The empty set $\varnothing$ means every branch has died, and a set is accepting exactly when it contains at least one accepting NFA state.

One-symbol set transition. For an NFA without $\epsilon$-transitions, the next possible-states set after reading $a$ from any state of $A$:

$$\widetilde{\delta}(A,a)=\bigcup_{q\in A}\delta(q,a)$$

Example 5. Computing set transitions.

Reading the table as a DFA, with one state per subset and start state $\{p\}$, gives the determinized machine. Only four of the $2^3=8$ subsets are reachable from $\{p\}$, and they already recognize the language:

Subset construction. Given an NFA without $\epsilon$-transitions $N=(Q_N,\Sigma,\delta_N,q_0,F_N)$, build the DFA $M=(Q_M,\Sigma,\delta_M,\{q_0\},F_M)$:

DFA part	Definition
$Q_M$	$2^{Q_N}$
$\delta_M(A,a)$	$\displaystyle\bigcup_{q\in A}\delta_N(q,a)$
start state	$\{q_0\}$
$F_M$	$\{A\subseteq Q_N\mid A\cap F_N\ne\varnothing\}$

The construction does not shrink the branching; it stores it. One DFA state is one complete set of live NFA branches.

The construction lists all $2^{|Q_N|}$ subsets, but only the subsets reachable from $\{q_0\}$ matter, as in Example 5. The exponential blow-up is sometimes unavoidable: for Example 3's language, a DFA must remember the last three symbols read, which is $2^3$ possibilities, while the NFA gets away with four states. NFAs can be exponentially smaller than any equivalent DFA, which is one reason they are worth designing with.

Extended transition functions. To compare the two machines on whole strings, extend both transition functions by the same last-symbol recursion used for DFAs. For the DFA $M$, whose states are subsets $A$:

$$\Delta_M(A,\epsilon)=A, \qquad \Delta_M(A,xa)=\delta_M(\Delta_M(A,x),a)$$

For the NFA $N$, acting on sets of states:

$$\Delta_N(A,\epsilon)=A, \qquad \Delta_N(A,xa)=\bigcup_{q\in\Delta_N(A,x)}\delta_N(q,a)$$

So $\Delta_N(\{q_0\},w)$ is exactly the possible-states set after reading $w$. Both functions also split over concatenation, $\Delta(A,xy)=\Delta(\Delta(A,x),y)$, by the same kind of induction.

Theorem: NFA-DFA equivalence. Every nondeterministic finite automaton has an equivalent deterministic finite automaton. Consequently, a language is regular if and only if some NFA recognizes it.

The proof is stated for NFAs without $\epsilon$-transitions; the closure paragraph below removes that assumption.

1. Lemma. For every subset $A\subseteq Q_N$ and every string $x$: $\Delta_M(A,x)=\Delta_N(A,x)$. The DFA's state after $x$ is exactly the NFA's possible-states set after $x$.

2. Base case. For $x=\epsilon$, both sides are $A$ by definition.

3. Inductive step. Write $x=ya$ with $a\in\Sigma$ and assume the lemma for $y$:

$$\begin{aligned} \Delta_M(A,ya) &=\delta_M(\Delta_M(A,y),a) && \text{definition of }\Delta_M\\ &=\delta_M(\Delta_N(A,y),a) && \text{induction hypothesis}\\ &=\Delta_N(\Delta_N(A,y),a) && \text{definition of }\delta_M\\ &=\Delta_N(A,ya) && \text{definition of }\Delta_N \end{aligned}$$

4. Conclusion. The machines agree on every string:

$$\begin{aligned} x\in L(M) &\iff \Delta_M(\{q_0\},x)\in F_M \iff \Delta_M(\{q_0\},x)\cap F_N\ne\varnothing\\ &\iff \Delta_N(\{q_0\},x)\cap F_N\ne\varnothing \iff x\in L(N) \end{aligned}$$

The first two steps unfold the construction's accepting set, the third is the lemma, and the last is the definition of NFA acceptance. Hence $L(M)=L(N)$.

Epsilon closure. For a set of states $A$, the set $E(A)$ of all states reachable from $A$ by zero or more $\epsilon$-transitions. To determinize an NFA with $\epsilon$-transitions, charge the free moves to the bookkeeping: start the DFA in $E(\{q_0\})$ and set

$$\delta_M(A,a)=E\Big(\bigcup_{q\in A}\delta_N(q,a)\Big).$$

The same induction then goes through unchanged, which is how Example 2's table already behaved: every row included the states reached by sliding along $\epsilon$-arrows.

Nondeterminism adds convenience, not power.

Concatenation with NFAs

Nondeterminism resolves the split problem that opened the lecture. The NFA for $L_1\circ L_2$ runs the first machine, guesses when the first part is finished, and jumps into the second machine by an $\epsilon$-transition.

Concatenation construction. Let $N_1=(Q_1,\Sigma,\delta_1,q_1,F_1)$ recognize $L_1$ and $N_2=(Q_2,\Sigma,\delta_2,q_2,F_2)$ recognize $L_2$, with disjoint state sets. Build $N$ for $L_1\circ L_2$:

Part of $N$	Definition
States	$Q_1\cup Q_2$
Start state	$q_1$
Accepting states	$F_2$
Old transitions	Keep all transitions of $N_1$ and $N_2$
New transitions	Add $\epsilon$-transitions from each state in $F_1$ to $q_2$

Written as one transition function:

$$\delta(q,a)= \begin{cases} \delta_1(q,a) & \text{if } q\in Q_1\setminus F_1,\\ \delta_1(q,a) & \text{if } q\in F_1 \text{ and } a\ne\epsilon,\\ \delta_1(q,a)\cup\{q_2\} & \text{if } q\in F_1 \text{ and } a=\epsilon,\\ \delta_2(q,a) & \text{if } q\in Q_2. \end{cases}$$

Only accepting states of $N_1$ may jump, and the jump reads nothing. Old accepting states of $N_1$ are no longer accepting in $N$, so finishing a string of $L_1$ proves nothing by itself; the rest of the input must still drive $N_2$ to $F_2$.

Recipe: proving an NFA construction correct. $L(N)=L_1\circ L_2$ needs two directions, and both are exchanges of witnesses.

1. Path to split. Take any accepting path of $N$. It must use exactly one $\epsilon$-jump, since the jump is the only way from $Q_1$ to the accepting states in $Q_2$. The jump marks a split $w=xy$ where $x$ drove $N_1$ to $F_1$, so $x\in L_1$, and $y$ drove $N_2$ to $F_2$, so $y\in L_2$.
2. Split to path. Take any $w=xy$ with $x\in L_1$ and $y\in L_2$. Glue the accepting run of $N_1$ on $x$, the $\epsilon$-jump, and the accepting run of $N_2$ on $y$ into one accepting path of $N$.

Closure under concatenation. If $L_1$ and $L_2$ are regular, then $L_1\circ L_2$ is regular: the construction gives an NFA for it, and every NFA has an equivalent DFA.

This is the general workflow the equivalence theorem unlocks: build with nondeterminism, conclude regularity for free. The remaining question is whether the whole approach has a ceiling: is every language regular, or does finite memory have a real limit?