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

AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.