Sol.

Step 01: Find ∈-closure of (q1), (q2) and (q3).

∈-closure of (q1) = {q1, q2, q3}

∈-closure of (q2) = {q2, q3}

∈-closure of (q3) = {q3}

For each state find the next state for each input. See the table below,

State | 0 | 1 | 2 |

->q1 | {q1,q2,q3} | {q2,q3} | {q3} |

q2 | φ | {q2,q3} | {q3} |

q3 | φ | φ | {q3} |

From the question diagram, it is clear that only with ∈ input q1 and q2 state can reach to the final state.

So, now without ∈ input, q1 and q2 is also treated as final states.

As shown in diagram below.

## Q1: What is an ε-transition in an NFA?

**Ans:** An ε-transition, also known as an epsilon-transition, is a transition in a non-deterministic finite automaton (NFA) that occurs without consuming any input symbol. An ε-transition allows the NFA to move from one state to another without reading any input.

## Q2: Why do we need to remove ε-transitions from an NFA?

**Ans:** ε-transitions can make the behavior of an NFA more complex and difficult to analyze. Removing ε-transitions can simplify the automaton and make it easier to understand and work with. Additionally, many algorithms for manipulating NFAs do not handle ε-transitions directly, so it is often necessary to remove them before applying these algorithms.

## Q3: How can you remove ε-transitions from an NFA?

**Ans:** The standard algorithm for removing ε-transitions from an NFA is called ε-closure. The ε-closure of a state is the set of all states that can be reached from that state by following any number of ε-transitions. To remove ε-transitions, we first compute the ε-closure of each state in the NFA. Then, for each transition in the NFA that has an ε-transition, we add new transitions that follow each possible path through the ε-closure of the source state to the target state, consuming one input symbol at a time.

## Q4: What is the resulting automaton called after removing ε-transitions from an NFA?

**Ans: **The resulting automaton is called an NFA without ε-transitions, or an NFAε. An NFAε is an NFA that does not contain any ε-transitions.

## Q5: Can an NFAε recognize the same language as the original NFA with ε-transitions?

**Ans:** Yes, an NFAε can recognize the same language as the original NFA with ε-transitions. This is because the ε-closure algorithm computes all possible paths through the ε-transitions, and the resulting NFAε includes all of these paths as explicit transitions.

## Q6: Does removing ε-transitions always result in a smaller NFA?

**Ans:** Not necessarily. In some cases, removing ε-transitions can actually result in a larger NFA, due to the need to add new transitions to represent all possible paths through the ε-closure of each state. However, the resulting NFA is typically simpler and easier to work with than the original NFA with ε-transitions.