Nondeterminism

NFAs, subset construction, and regular operations

Adding nondeterminism

A deterministic machine has exactly one possible next move at every step. A nondeterministic machine may have several possible next moves—or none at all.

A DFA permits exactly one transition for each state-symbol pair, while an NFA may offer multiple choices.

Nondeterminism does not mean randomness. An NFA accepts an input if at least one possible computation path reaches an accepting state after consuming the input.

Two thought experiments can help us interpret this:

• Omnipotent interpretation: Whenever the machine has several choices, it splits into copies that explore every option. The input is accepted if any copy accepts.
• Omniscient interpretation: Whenever the machine has a choice, it somehow guesses a successful path whenever one exists.

Neither interpretation describes how ordinary hardware literally operates. Both capture the same mathematical acceptance rule.

Why nondeterminism is useful

Nondeterminism often makes a machine easier to design because it lets the machine “guess” which part of the input is important and then verify that guess.

For example, a deterministic machine searching for a pattern must track all relevant partial matches. An NFA can begin a new possible match whenever it encounters a promising symbol.

Examples originally used to motivate nondeterministic choices in practice.

The value of NFAs is therefore not greater computational power. It is often a simpler description of the same computation.

A first NFA

An example NFA with three states.

In an NFA:

• a state may have multiple outgoing transitions bearing the same symbol;
• a state may lack a transition for a symbol; and
• a transition may be labeled \(\varepsilon\), allowing it to be followed without consuming input.

The machine accepts if there is at least one path from the start state to an accepting state whose non-\(\varepsilon\) labels spell the complete input.

Epsilon transitions

An \(\varepsilon\)-transition is a free move: it changes the current state without consuming a symbol.

An NFA containing an epsilon transition.

Whenever a computation reaches a state with outgoing \(\varepsilon\)-transitions, every state reachable through zero or more such transitions becomes a current possibility.

The epsilon closure of a state \(q\), written \(E(q)\), is the set containing \(q\) and every state reachable from \(q\) using only \(\varepsilon\)-transitions. For a set \(R\subseteq Q\),

\[ E(R)=\bigcup_{q\in R}E(q). \]

Tracing an NFA

When tracing an input, maintain the set of all states the machine could currently occupy.

1. Begin with the epsilon closure of the start state.
2. For each input symbol, follow every matching transition from every current state.
3. Take the epsilon closure of all resulting states.
4. Accept if the final set contains at least one accepting state.

Tracing the input 010110 through all possible paths. A failed branch does not reject the input if another branch reaches an accepting state.

The important question is not whether every path succeeds, but whether any path reaches an accepting state.

Formal definition of an NFA

A nondeterministic finite automaton is a five-tuple

\[ N=(Q,\Sigma,\delta,q_0,F), \]

where:

• \(Q\) is a finite set of states;
• \(\Sigma\) is a finite input alphabet;
• \(\delta:Q\times(\Sigma\cup\{\varepsilon\})\rightarrow\mathcal{P}(Q)\) is the transition function;
• \(q_0\in Q\) is the start state; and
• \(F\subseteq Q\) is the set of accepting states.

Here \(\mathcal{P}(Q)\) is the power set of \(Q\): the set of all subsets of \(Q\).

The essential difference from a DFA is the transition function’s output:

Model	Transition function	Result
DFA	\(\delta:Q\times\Sigma\rightarrow Q\)	one state
NFA	\(\delta:Q\times(\Sigma\cup\{\varepsilon\})\rightarrow\mathcal{P}(Q)\)	a set of possible states

The NFA computation model

Extend \(\delta\) so that it processes entire strings:

\[ \delta^*:Q\times\Sigma^*\rightarrow\mathcal{P}(Q). \]

Base case

Before reading input, the machine may follow any available epsilon transitions:

\[ \delta^*(q,\varepsilon)=E(q). \]

Recursive case

For \(w\in\Sigma^*\) and \(a\in\Sigma\),

\[ \delta^*(q,wa) = E\left( \bigcup_{r\in\delta^*(q,w)}\delta(r,a) \right). \]

Thus, an NFA accepts \(w\) precisely when at least one reachable state is accepting:

\[ w\in L(N) \iff \delta^*(q_0,w)\cap F\neq\varnothing. \]

Compare this with the DFA rule:

\[ w\in L(A) \iff \delta^*(q_0,w)\in F. \]

A DFA ends in one state; an NFA ends with a set of possible states.

Comparing the power of machine models

Suppose \(A\) and \(B\) denote two categories of machines, such as DFAs and NFAs.

• \(B\) is no more powerful than \(A\) if every language recognized by a \(B\) can also be recognized by some \(A\).
• \(B\) is strictly less powerful than \(A\) if the condition above holds and some language recognized by an \(A\) cannot be recognized by any \(B\).
• \(A\) and \(B\) have equal power if each can recognize every language recognized by the other.

Equality of computational power does not mean the models are equally convenient or equally concise. One may require far fewer states than the other.

Are NFAs more powerful than DFAs?

To prove that DFAs and NFAs recognize the same languages, we must prove both containments:

\[ \mathcal{L}(\mathrm{DFA})\subseteq\mathcal{L}(\mathrm{NFA}) \]

and

\[ \mathcal{L}(\mathrm{NFA})\subseteq\mathcal{L}(\mathrm{DFA}). \]

Here \(\mathcal{L}(\mathrm{DFA})\) denotes the class of languages recognized by DFAs, not the language of one particular machine.

Every DFA is an NFA

The first containment is immediate. Given a DFA

\[ A=(Q,\Sigma,\delta,q_0,F), \]

construct the NFA

\[ N=(Q,\Sigma,\delta',q_0,F), \]

where, for every \(q\in Q\),

\[ \delta'(q,\varepsilon)=\varnothing \]

and, for every \(a\in\Sigma\),

\[ \delta'(q,a)=\{\delta(q,a)\}. \]

The NFA simply never uses its additional choices. Therefore,

\[ \mathcal{L}(\mathrm{DFA})\subseteq\mathcal{L}(\mathrm{NFA}). \]

Every NFA has an equivalent DFA

The reverse direction uses the subset construction. A state in the new DFA represents the entire set of states the NFA could occupy after reading the same input.

Given

\[ N=(Q,\Sigma,\delta,q_0,F), \]

construct

\[ D=(Q',\Sigma,\delta',q_0',F') \]

as follows.

DFA states

\[ Q'=\mathcal{P}(Q). \]

In principle, an \(n\)-state NFA can produce as many as \(2^n\) DFA states. In practice, construct only the subsets reachable from the start state.

The empty subset \(\varnothing\) acts as a dead state.

Start state

\[ q_0'=E(q_0). \]

The DFA begins in every NFA state reachable from \(q_0\) without consuming input.

Transition function

For a subset \(R\subseteq Q\) and symbol \(a\in\Sigma\),

\[ \delta'(R,a) = E\left( \bigcup_{r\in R}\delta(r,a) \right). \]

Accepting states

Any subset containing an NFA accepting state must be accepting:

\[ F'=\{R\subseteq Q:R\cap F\neq\varnothing\}. \]

Why the construction works

For every input string \(w\), the DFA state reached after reading \(w\) is exactly the set of states the NFA could reach after reading \(w\):

\[ \delta_D^*(q_0',w)=\delta_N^*(q_0,w). \]

This statement can be proved by induction on the length of \(w\).

• Base: For \(w=\varepsilon\), both sides equal \(E(q_0)\).
• Inductive hypothesis: Assume the equality holds for some \(w\).
• Inductive step: For any \(a\in\Sigma\), apply the subset transition rule to show that the equality also holds for \(wa\).

Because the DFA accepts exactly those subsets that intersect \(F\), the two machines accept precisely the same strings. Therefore,

\[ \mathcal{L}(\mathrm{NFA})\subseteq\mathcal{L}(\mathrm{DFA}). \]

Together, the two containments establish

\[ \mathcal{L}(\mathrm{NFA})=\mathcal{L}(\mathrm{DFA}). \]

Example of the subset construction

Begin with this three-state NFA:

A three-state NFA to be converted into a DFA.

The possible DFA states are subsets of \(\{1,2,3\}\):

\[ \varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}. \]

Only subsets reachable from the start subset need to be retained.

The completed NFA-to-DFA conversion. Each red DFA state represents a set of blue NFA states.

After conversion, ordinary DFA minimization may reveal that some states are equivalent and can be combined.

Example with an epsilon transition

An NFA whose start state’s epsilon closure contains more than one state.

For an NFA with \(\varepsilon\)-transitions, remember to take epsilon closure:

• when determining the DFA start state; and
• after following transitions for every input symbol.

What equivalence does—and does not—mean

NFAs and DFAs have equal computational power: both recognize exactly the regular languages.

However:

• an NFA may use substantially fewer states than an equivalent DFA;
• an NFA can be easier to design and understand;
• a DFA gives a direct implementation with one active state at a time; and
• conversion from an NFA to a DFA may cause an exponential increase in states.

NFAs are therefore valuable tools even though they do not enlarge the class of recognizable languages.

Revisiting closure properties

Nondeterminism provides elegant constructions proving that the regular languages are closed under union, concatenation, and Kleene star.

Suppose \(M_1\) and \(M_2\) recognize regular languages \(A_1\) and \(A_2\).

Closure under union

To recognize \(A_1\cup A_2\):

1. create a new start state;
2. add \(\varepsilon\)-transitions from it to the start states of \(M_1\) and \(M_2\); and
3. retain the accepting states of both machines.

The NFA nondeterministically chooses which machine to simulate. It accepts precisely when the input belongs to at least one of the two languages.

Because every NFA has an equivalent DFA, \(A_1\cup A_2\) is regular.

For intersection, one may use the product construction or De Morgan’s law:

\[ A_1\cap A_2=\overline{\overline{A_1}\cup\overline{A_2}}. \]

Closure under concatenation

To recognize \(A_1A_2\):

1. begin with \(M_1\) and \(M_2\);
2. change each accepting state of \(M_1\) into a nonaccepting state; and
3. add an \(\varepsilon\)-transition from each former accepting state of \(M_1\) to the start state of \(M_2\).

The machine can move from \(M_1\) to \(M_2\) whenever the prefix read so far belongs to \(A_1\). It accepts when the remaining suffix belongs to \(A_2\).

This construction handles all possible split points nondeterministically.

Closure under Kleene star

To recognize \(A_1^*\):

1. create a new start state and make it accepting, ensuring that \(\varepsilon\) is accepted;
2. add an \(\varepsilon\)-transition from the new start state to the original start state; and
3. add \(\varepsilon\)-transitions from the original accepting states back to the original start state.

Each return to the original start begins another concatenated string from \(A_1\). The construction therefore accepts zero or more repetitions.

Union, concatenation, and star are called the regular operations.

Design exercises

1. Construct an NFA for the union of:
   • \(A_1=\) strings that do not contain 00;
   • \(A_2=\) strings that end in 01.
2. Construct an NFA for \(A_1A_2\) using the same languages.
3. Let \(L\) contain strings beginning with 1 and ending with 0. Construct an NFA for \(L^*\).
4. Convert each NFA to a DFA using the subset construction. Include epsilon closure at every required step.

Check your understanding

1. Why does one failed NFA path not necessarily cause rejection?
2. Why is an NFA transition’s output a set of states?
3. What does a state in the subset-construction DFA represent?
4. Which subsets become accepting DFA states?
5. If NFAs and DFAs recognize the same languages, why are NFAs still useful?