NFA with ∈ to DFA Indirect Method

Indirect Method: In this method,

Step 01: Convert NFA with ∈ moves to NFA without ∈ moves.

Step 02: Than NFA without ∈ moves is converted to the DFA.

For example: Convert he following NFA with ε in to DFA using Indirect method of comversion ?

Solution: Step 01: Convert NFA with ∈ moves to NFA without

∈ moves.∈-Closure of q0: {q0, q1, q2}

∈-Closure of q1: {q1, q2}

∈-Closure of q2: {q2}

State	a	b	C
è q0	{q0, q1, q2}	{q1, q2}	{q2}
q1	Φ	{q1, q2}	{q2}
q2	Φ	Φ	{q2}

NFA without ∈ Transition table
Step 02: NFA without ∈ moves is converted to the DFA using Subset construction method.

State	a	b	C
{q0}	{q0, q1, q2}	{q1, q2}	{q2}
{q1}	DeadState	{q1, q2}	{q2}
{q2}	DeadState	DeadState	{q2}
{q0, q1, q2}	{q0, q1, q2}	{q1, q2}	{q2}
{q1, q2}	DeadState	{q1, q2}	{q2}
DeadState	DeadState	DeadState	DeadState

---

Q1: What is an NFA with ε-transitions?

Ans: An NFA with ε-transitions, also known as an NFAε, is a non-deterministic finite automaton that can transition between states without consuming any input symbols.

Q2: What is the indirect method for converting an NFAε to a DFA?

Ans: The indirect method for converting an NFAε to a DFA involves first converting the NFAε to an equivalent NFA without ε-transitions, and then applying the subset construction algorithm to convert the resulting NFA to a DFA.

Q3: How do you convert an NFAε to an equivalent NFA without ε-transitions?

Ans: To convert an NFAε to an equivalent NFA without ε-transitions, you need to first compute the ε-closure of each state in the NFAε. Then, for each state in the NFAε and each input symbol, you need to compute the set of states that can be reached from that state by following one or more input symbols and/or ε-transitions. These sets of states become the new states in the resulting NFA without ε-transitions.

Q4: What is the ε-closure of a state in an NFAε?

Ans: The ε-closure of a state in an NFAε is the set of all states that can be reached from that state by following any number of ε-transitions.