Back to the 2025 paper

Module 1: Introduction & Regular Languages

20252m

The ϵ\epsilon-closure of a state is

(i) The set of states reachable using ϵ\epsilon only
(ii) The set of unreachable states
(iii) The set of final states
(iv) The dead states

Worked SolutionAI Assisted

Answer

Correct Option: (i) The set of states reachable using ϵ\epsilon only

Explanation

ϵ\epsilon-closure ECLOSE(q)\text{ECLOSE}(q) for NFA-ϵ\epsilon:

ECLOSE(q)={p∣q→ϵ∗p}\text{ECLOSE}(q) = \{ p \mid q \xrightarrow{\epsilon^*} p \} — all states reachable from qq by zero or more ϵ\epsilon-moves, including qq itself.

Example: q0→ϵq1→ϵq2q_0 \xrightarrow{\epsilon} q_1 \xrightarrow{\epsilon} q_2 → ECLOSE(q0q_0) = {q0,q1,q2}\{q_0,q_1,q_2\}.

Used in subset construction for ϵ\epsilon-NFA → DFA/NFA conversion: δD(S,a)=ECLOSE(⋃q∈Sδ(q,a))\delta_D(S,a) = \text{ECLOSE}(\bigcup_{q\in S} \delta(q,a)).

Other options are incorrect: not unreachable, not just finals, not dead states.

Final Answer

ϵ\epsilon-closure = states via ϵ\epsilon only → Option (i).

Similar questions

Student FinanceWeb Platform

Pocketly — Personal Finance for Students

Keep your hostel and college expenses under control. Track accounts, log spending in seconds, and stay within your monthly budget.