What is the epsilon NFA?

Overview

An epsilon nondeterministic finite automaton (NFA) has null or epsilon transitions from one state to another. Epsilon NFA is also called a null NFA or an NFA lambda.

A regular expression for a language forms an epsilon NFA. This epsilon NFA then converts to a simple NFA. We then use the simple NFA to make a deterministic finite automaton (DFA).

Null closure

We require null closure to convert an epsilon NFA to an NFA. Moreover, it shows us the states we can transcend due to a null transition.

Note: We can visit here to learn how to convert an epsilon NFA to NFA.

Let's suppose an NFA $<Q, Σ, q0_​, δ, F>$ and $S \subseteq Q$ is a defined set of states, where:

• $Q$ is the finite set of states
• $Σ$ is the input symbols
• $q_0$ is the start state
• $δ$ is the transition function
• $F$ is the final state

The null closure of $S$ is the set $Λ(S)$. We can define it recursively as follows:

1. $S \subseteq Λ(S)$
2. For every $q \in Λ(S)$, $δ(q, Λ) \subseteq Λ(S)$

Example

Consider the following epsilon NFA, where $q_0$ is the start state.

The null closure of the NFA is as follows:

We determine this null closure by how a transition transcends from one state to another with a null input.