CSE331 Automata and Computability
Lecture 8.1: NFA with 𝜀 Transitions
Presenter: Warida Rashid Scribe: Warida Rashid
Epsilon NFA (𝜀-NFA)
The class of NFAs can be extended by allowing spontaneous transitions without reading any
input symbols. In the diagram, such transitions are represented by an edge labeled by epsilon (𝜀).
It is important to note that, 𝜀 is not considered as an input symbol. In fact, it is assumed that 𝜀
does not belong to any input alphabet. An NFA with epsilon transition(s) is called 𝜀-NFA. Both
NFAs and 𝜀-NFAs recognize the same class of languages that are defined as Regular
Languages. However, allowing transitions on epsilon adds certain programming conveniences.
Example Simulation
Consider the following 𝜀-NFA.
When the automaton is at state A, it “copies” itself. One of the copies remain at A and the other
one goes to B following the epsilon(𝜀) transition from A to B. Again, when the automaton is at
state B, it “copies” itself. One of the copies remain at B and the other one goes to C following the
epsilon(𝜀) transition from B to C. Basically, When the automaton is at state A, after completing
the epsilon transitions, the states that the automaton is at are: A, B, C. This is called the
epsilon(𝜀) closure. 𝜀-Closure of a state q is the set of states that can be reached from q by
following the epsilon transitions and it includes the state q itself. According to the definition,
𝜀-Closure of A is the set {A, B, C} and the 𝜀-Closure of B is the set {B, C}.
If we process the string 010 can be represented by the following diagram:
Language of an NFA/𝜀-NFA
The language of an NFA/𝜀-NFA is the set of strings that it accepts. A string w is accepted by an
NFA if δ(q0, w) contains a final/accepting state.
Comparison between DFA and NFA/𝜀-NFA
● A DFA cannot be in more than one state at any given point but an NFA/𝜀-NFA can.
● DFA does not allow moving to two or more different states, from the same state, on the
same input symbol but an NFA/𝜀-NFA does.
● In DFA, the transition function is
𝜹:𝑸 × ∑ → 𝑸
In NFA/𝜀-NFA, the transition function is
𝜹:𝑸 × ∑ → P(𝑸)
Here, P(𝑸) is the power set of Q.
● Determinism does not allow epsilon transitions but nondeterminism does.
____________