Introduction to NFAs with Epsilon-Transitions

In our previous lessons, you became proficient in analyzing and designing Deterministic Finite Automata. You learned that the core of DFA design is encoding the necessary memory of the input seen so far into the machine's states. While DFAs are foundational, you may have noticed that designing them for certain languages, especially those involving "or" conditions or searching for patterns, can become quite intricate.

This lesson introduces a powerful and elegant extension to finite automata: nondeterminism. A Nondeterministic Finite Automaton (NFA) can have multiple possible computations for a single input string. This ability to "guess" or explore several paths at once often makes designing an automaton vastly simpler and more intuitive. We will formally define what an NFA is, see how it computes, and then introduce a special feature called epsilon (ε) transitions—moves that can be made without consuming any input. Your goal is to understand the formal definitions of these machines and the mechanics of their operation.

The Power of Nondeterminism

In a DFA, for any given state and input symbol, there is exactly one state to which the machine can transition. Nondeterminism relaxes this constraint in two key ways:

A state can have multiple possible next states for a single input symbol.
A state can have zero next states for an input symbol, causing that particular computation path to "die".

Imagine you are designing a machine to recognize all strings over ${0, 1}$ that have a 1 in the second-to-last position. With a DFA, you'd need to keep track of whether you've seen a 1 and what the last symbol was. With an NFA, the logic is much more direct: "scan the string, and at some point, guess that you're at the second-to-last symbol. If that symbol is a 1, read one more symbol and then accept."

The following video provides an excellent motivation for NFAs, showing how they can express complex languages more simply than their deterministic counterparts.

Lecture 6/65: Nondeterministic Finite State Machines: Formal Definition

This video, "Nondeterministic Finite State Machines: Formal Definition," begins by contrasting a simple, intuitive NFA with a more complex but equivalent DFA for the same language.

Please watch the first part of the video, from the beginning to the challenge. Pay close attention to the two examples presented: The language of strings with a 0 in the second-to-last position. The language of strings containing either 010 or 0111. Notice how the NFAs seem to "guess" where the pattern begins and which pattern to look for, making their design much more straightforward.

Formal Definition of an NFA

Now, let's formalize this notion. An NFA is, like a DFA, a 5-tuple. Four of the five components are identical. The difference, as you might expect, lies in the transition function, $δ$ .

Since a transition from a state can lead to a set of next states, the codomain (output) of the transition function must be a set of states. Specifically, it is the power set of the set of all states, Q. Given your mathematical background, you'll recall that the power set of Q, denoted $P (Q)$ or $2^{Q}$ , is the set of all subsets of Q.

The following video provides a quick but essential refresher on power sets before giving the formal definition of an NFA.

Lecture 6/65: Nondeterministic Finite State Machines: Formal Definition

This segment clarifies what a power set is and why it's the correct mathematical tool to describe the behavior of an NFA's transition function.

Watch the segment on power sets. The explanation of how to count the number of subsets using a binary string analogy is a classic computer science perspective that should resonate with your background.

With the power set concept fresh in your mind, we can now define an NFA. A Nondeterministic Finite Automaton (NFA) is a 5-tuple $M = (Q, Σ, δ, q_{0}, F)$ , where:

$Q$ is a finite set of states.
$Σ$ is a finite alphabet.
$δ : Q \times Σ \to P (Q)$ is the transition function.
$q_{0} \in Q$ is the start state.
$F \subseteq Q$ is the set of accept states.

The key distinction from a DFA is the transition function, $δ (q, a) = {q_{1}, q_{2}, \dots, q_{k}}$ , which returns a set of states.

The following video walks through this formal definition, deriving the need for the power set from a concrete example.

Formal Definition of Non-Deterministic Finite Automata (NFA)

This Neso Academy video provides a clear, step-by-step derivation of the NFA's formal definition. It begins with an example, contrasts it with a DFA, and builds up to the formal 5-tuple, paying special attention to the transition function.

Watch the entire video. The initial example highlights the key differences from a DFA: multiple next states are possible, and some transitions can be undefined (leading to the empty set \emptyset). The video then builds up the formal definition, justifying why the transition function \delta must map to \mathcal{P}(Q) (which the video calls 2^Q).

An NFA accepts an input string $w$ if there exists at least one sequence of choices that leads from the start state to an accept state after processing all symbols of $w$ . If all possible computation paths end in non-accepting states or get "stuck" (transition to $\emptyset$ ), the string is rejected.

Epsilon (ε) Transitions: The "Free Move"

We can make NFAs even more flexible by adding one more feature: the ability to change state without consuming an input symbol. These are called epsilon (ε) transitions.

On the top, a standard NFA recognizes the language `{ab}`. On the bottom, an ε-NFA recognizes the same language. The transition from q1 to q2 is an ε-transition, a "free move" that doesn't consume an input character.

At first, this might seem like a minor addition, but ε-transitions are incredibly useful for building complex machines by composing smaller ones. For example, to recognize the union of two languages, $L_{1} \cup L_{2}$ , you can create an NFA for each and then join them with a new start state that has ε-transitions to the start states of the original two machines.

To accommodate this, we must update our formal definition. An NFA with epsilon transitions (often called an ε-NFA) is a 5-tuple $M = (Q, Σ, δ, q_{0}, F)$ where the only change is to the domain of the transition function:

$δ : Q \times (Σ \cup {ϵ}) \to P (Q)$

The transition function can now take $ϵ$ as a valid input alongside symbols from the alphabet $Σ$ .

Lecture 5 – ϵ-Nondeterministic Finite Automata (ϵ-NFA)

These lecture slides from Korea University provide a concise and formal introduction to ε-NFAs.

Please read the first few sections of the slides: Start with the section "ϵ-Transition" on slide 5 for the initial concept. Next, read the formal definition of an ε-NFA on slide 6. Note the change in the transition function's domain. Finally, examine the section "Transition Diagram and Transition Table" on slide 8 to see how an ε-NFA is represented.

Computation with Epsilon-Closures

The presence of ε-transitions complicates the notion of the "current state" of the machine. If a machine is in a state $q$ , it can instantly and freely move to any state reachable from $q$ via a path of ε-transitions. Therefore, we must consider the machine to be in all these states simultaneously. This concept is captured by the epsilon-closure.

The epsilon-closure of a state $q$ , denoted $E C l o (q)$ , is the set of states containing $q$ itself, plus all states that can be reached from $q$ by following one or more ε-transitions.

Lecture 5 – ϵ-Nondeterministic Finite Automata (ϵ-NFA)

This section of the lecture slides formally defines the epsilon-closure and provides clear examples.

Please read the section titled "ϵ-Closures" on slide 9 for the inductive definition. Then, work through the example on slide 10 to solidify your understanding.

Let's apply this concept to the automaton below.

An ε-NFA with states q0, q1, and q2. An ε-transition connects q0 to q1.

What is the epsilon-closure of state $q_{0}$ ?

$q_{0}$ is in $E C l o (q_{0})$ by definition.
From $q_{0}$ , we can reach $q_{1}$ via one ε-transition. So, $q_{1}$ is also in $E C l o (q_{0})$ .
From $q_{1}$ , there are no outgoing ε-transitions.
Therefore, $E C l o (q_{0}) = {q_{0}, q_{1}}$ .

The computation of an ε-NFA on an input string $w$ proceeds as follows:

Start with the set of current states as $E C l o (q_{0})$ .
For each symbol $c$ in $w$ :
a. Find all states reachable from the current set of states by following a transition on $c$ . Let's call this new set $S_{n e x t}$ .
b. The next set of current states becomes the epsilon-closure of every state in $S_{n e x t}$ .
After the last symbol of $w$ is processed, if the final set of current states has a non-empty intersection with the set of accept states $F$ , the string is accepted.

This process is formalized using an extended transition function, $δ^{*}$ . For an ε-NFA, its definition incorporates the epsilon-closure at each step.

Lecture 5 – ϵ-Nondeterministic Finite Automata (ϵ-NFA)

These final sections give the formal definitions for the extended transition function and acceptance in an ε-NFA, which capture the computational process we just described.

Read the formal definition of the extended transition function on slide 14. Then, read the definitions for acceptance and language on slide 15.

Conclusion

In this lesson, we have expanded our view of finite automata to include the powerful concept of nondeterminism. You've seen that allowing a machine to have choices can lead to much simpler and more intuitive designs for certain languages.

Here are the key takeaways:

Nondeterminism allows a machine to have multiple (or zero) possible transitions from a state on a given input symbol.
The formal definition of an NFA differs from a DFA primarily in its transition function, $δ$ , which maps to the power set of states: $δ : Q \times Σ \to P (Q)$ .
Epsilon (ε) transitions are "free moves" that allow a state change without consuming an input symbol. They are formalized by expanding the domain of the transition function: $δ : Q \times (Σ \cup {ϵ}) \to P (Q)$ .
Computation in an ε-NFA requires the use of the epsilon-closure ( $E C l o$ ) to account for all states that are reachable at any moment.

You might be wondering if this new flexibility gives NFAs more computational power than DFAs. The perhaps surprising answer is no. In our next lesson, we will explore the subset construction algorithm, a fundamental procedure for converting any NFA into an equivalent DFA. This will prove that DFAs and NFAs are equal in their power to recognize languages.

Recommended resources

The Power of Nondeterminism

Formal Definition of an NFA

Epsilon (ε) Transitions: The "Free Move"

Computation with Epsilon-Closures

Conclusion