NFA and epsilon-NFA

Why it exists

A DFA must commit at every step. Many languages are easier to describe if the machine may guess: "the third symbol from the end is a $1$" is simple for a machine that guesses that this $1$ is the third from the end and then checks that exactly two symbols follow. A nondeterministic finite automaton (NFA) has that freedom. Nondeterminism does not let finite automata recognise more languages (the subset construction turns every NFA into a DFA) but it makes machines smaller and constructions simpler, and the idea returns for pushdown automata, where it does add power.

Prerequisites

You need the DFA (DFA).

Precise definitions

NFA. $N = (Q, \Sigma, \delta, q_0, F)$ as for a DFA, except that $\delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$ returns a set of states (possibly empty). A move on $\varepsilon$ consumes no input symbol. If no $\varepsilon$ move exists the machine is an NFA without $\varepsilon$; the general machine is sometimes called an $\varepsilon$-NFA.

Computation. For an input $w = a_1 a_2 \cdots a_n$, a computation is a sequence of states $r_0 = q_0, r_1, \ldots, r_m$ in which each step either follows an $\varepsilon$ edge or reads the next input symbol, and all $n$ symbols are read. It is accepting if it ends in an accepting state.

Acceptance. $N$ accepts $w$ if at least one computation on $w$ is accepting; it rejects $w$ if every computation fails (ends in a non-accepting state or gets stuck). $L(N)$ is the set of accepted strings.

Epsilon closure. $\operatorname{ECLOSE}(S)$ is the set of states reachable from the states of $S$ by following $\varepsilon$ edges only (zero or more of them); it contains $S$ itself.

Extended transition function. $\hat\delta(q, \varepsilon) = \operatorname{ECLOSE}(\{q\})$ and $\hat\delta(q, wa) = \operatorname{ECLOSE}\bigl(\bigcup_{p \in \hat\delta(q, w)} \delta(p, a)\bigr)$. Then $w \in L(N)$ iff $\hat\delta(q_0, w) \cap F \ne \emptyset$.

How it works

Nondeterminism is parallel exploration

There is no magic and no probability: think of the NFA as exploring all choices at once, or as a machine that can duplicate itself at every branching, each copy following one choice. Copies die when they have no move. The string is accepted if some copy is in an accepting state when the input ends. Equivalently, one can simulate the NFA by keeping the set of active states: start with $\operatorname{ECLOSE}(\{q_0\})$, and for each symbol replace the set $S$ by $\operatorname{ECLOSE}(\bigcup_{p \in S} \delta(p, a))$. This simulation takes time $O(|w| \cdot |Q|^2)$ and memory $O(|Q|)$ and is exactly what the animations show.

Example 1: ends with 01

Three states: $p$ loops on $0$ and $1$ (waiting), on $0$ it may also guess "this $0$ is the second-last symbol" and move to $q$; $q$ moves to the accepting $r$ on $1$. On the input $1001$ the active sets are $\{p\}$, $\{p\}$, $\{p, q\}$, $\{p, q\}$, $\{p, r\}$: the last set contains the accepting state $r$, so the string is accepted.

Example 2: the third symbol from the end is 1

Four states: $p$ loops on everything; on $1$ it may move to $s_1$ (guess: this is the third-last symbol); $s_1$ and $s_2$ move on either symbol; $s_3$ is accepting. The machine can only accept if exactly two symbols follow the guessed $1$. A DFA for this language needs $8$ states (it must remember the last three symbols); the NFA needs $4$.

Example 3: union by guessing, contains 00 or 11

The NFA starts in $s$, which loops forever; on $0$ it can guess "a $00$ starts here" and go to $a$, on $1$ to $b$; then it checks the next symbol and falls into the accepting, looping state $t$. Two simple machines are glued by letting the start state choose between them. On $01011$: $\{s\}$, $\{a, s\}$, $\{s, b\}$, $\{a, s\}$, $\{s, b\}$, $\{b, s, t\}$.

Epsilon moves

An $\varepsilon$ edge lets the machine change state without reading anything. It is most useful for gluing: to accept $L_1 \cup L_2$ make a new start state with $\varepsilon$ edges to the starts of the two machines; for $L_1 L_2$ add $\varepsilon$ edges from the accepting states of the first to the start of the second; for $L^*$ add $\varepsilon$ edges back to the start. Following $\varepsilon$ edges repeatedly gives the closure: in the machine below the closure of $i$ is $\{i, a_1, b_1\}$, of $a_2$ it is $\{a_2, c_1, f\}$ and of $c_2$ it is $\{c_1, c_2, f\}$. The machine recognises $(a \mid b)\, c^*$; on $bcc$ the sets are first the closure of $i$, then the $b$-move and its closure, and so on.

The smaller machine for $a^* b^*$ shows a single $\varepsilon$ edge from the loop on $a$ to the loop on $b$:

What nondeterminism does and does not change

• Same languages. Every NFA (with or without $\varepsilon$) has an equivalent DFA, so the languages accepted are exactly the regular languages. Nondeterminism saves states: the $n$-th symbol from the end is $1$ needs $n + 1$ NFA states and $2^n$ DFA states.
• Removing $\varepsilon$ moves without adding states: let $\delta'(q, a) = \operatorname{ECLOSE}(\operatorname{move}(\operatorname{ECLOSE}(\{q\}), a))$ and make a state accepting if its closure contains an accepting state. The result accepts the same language (checked on random machines).
• One accepting state can be arranged for an $\varepsilon$-NFA (add a new accepting state with $\varepsilon$ edges from the old ones) but not always for an NFA without $\varepsilon$ (the language $\{\varepsilon, a\}$ needs two).
• Complement is not easy: swapping accepting and non-accepting states of an NFA does not give the complement, because a string is accepted if some computation accepts, so after the swap it is accepted if some computation rejects. Determinise first.
• Reversal is easy: reverse every edge, swap start and accepting states (adding $\varepsilon$ edges if there are several accepting states).
• Testing acceptance of a given string is cheap (the set simulation above), but the number of computations can be exponential.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The NFA is the intermediate form in converting regular expressions to automata; it is turned into a DFA by the subset construction. The same "accept if some computation accepts" idea defines the pushdown automaton, where nondeterminism really adds power.

PYQs

Consider the following two finite automata D1  and
D2  (as shown in the figure).

Which of the following statements is/are true?

Let M be the 5-state NFA with ε-transitions shown in the
diagram below

Which one of the following regular expressions
represents the language accepted by M ?

Let
δ
denote
the
transition
function
and
δ̂ denote the extended transition function of the
ε-NFA whose transition table is given below:

δ
ε
a
b
→ q0 {q2} {q1} {q0}
q1
{q2} {q2} {q3}
q2
{q0} ∅
∅
q3
∅
∅
{q2}

Then δ̂ (q2 , aba) is:

Consider
the
following
two
statements:
I. If all states of an NFA are accepting states then the
language
accepted
by
the
NFA
is
Σ*.
II. There exists a regular language A such that for all
languages B, A ∩B is regular.
Which one of the following is CORRECT?

Consider the finite automaton in the following figure.
What is the set of reachable states for the input string
0011?

What is the complement of the language accepted by the
NFA shown below?
Assume Σ = {a} and ε is the empty string.

Let w be any string of length n is {0, 1}*. Let L be the set
of all substrings of w. What is the minimum number of
states in a non-deterministic finite automaton that accepts
L?

Consider the following two finite automata. M1 accepts L1
and M2 accepts L2

Which one of the following is TRUE?

Consider the regular expression
 R = (a + b)*(aa + bb)(a + b)*
Which of the following non-deterministic finite
automata recognizes the language defined by the
regular expression R?
Edges labelled λ denote transitions on the empty
string.

Consider the non-deterministic finite automaton
(NFA) shown in the figure.

State X is the starting state of the automaton. Let the
language accepted by the NFA with Y as the only
accepting state be L1. Similarly, let the language
accepted by the NFA with Z as the only accepting state
be L2. Which of the following statements about L1 and
L2 is TRUE?

Self-check

Revision card

References