Converting a Given $\varepsilon$-NFA to a DFA via $\varepsilon$-Closures

You are given the following $\varepsilon$-NFA (states: $\{p,q,r\}$; alphabet: $\{a,b\}$):

• Start state: $p$
• Accepting (final) states: not explicitly stated in the prompt, so conversion is about the transition structure only (final states can be derived if you later specify which are accepting).

Transitions:

We will:

1. Compute all reachable $\varepsilon$-closures of NFA state sets.
2. Use subset construction to build the equivalent DFA, where each DFA state is a set of NFA states (a subset).

Key definitions used throughout:

• [epsilon-closure]{def="The set of NFA states reachable from a state (or set) using only $\varepsilon$-moves"}
• subset construction
• DFA transition function

Core conversion rule (what we compute)

For any set of NFA states $S$ and input symbol $x\in\{a,b\}$, the DFA transition is:

$$\delta_{\text{DFA}}(S,x) = \varepsilon\text{-closure} \Big( \bigcup_{s\in S}\delta_{\text{NFA}}(s,x) \Big)$$

So the workflow is:

• Move on symbol $x$ using the NFA’s labeled transitions: $\bigcup_{s\in S}\delta_{\text{NFA}}(s,x)$
• Then “expand” by following any number of $\varepsilon$-moves via $\varepsilon$-closure.

We’ll compute these exactly for the given machine.

Step 1 results (individual closures)

$$\varepsilon\text{-closure}(p)=\{p,q,r\}$$ $$\varepsilon\text{-closure}(q)=\{q\}$$ $$\varepsilon\text{-closure}(r)=\{p,q,r\}$$

Now we must compute closures of sets that arise during subset construction. (A set closure is the union of closures of its members, then expanded consistently.)

[set $\u03b5$-closure]{def="Closure of a set S is the union of individual closures of states in S"}

Step 2 details: transitions

Let the current DFA state be the subset $S$ of NFA states.

From $S_0=\{p,q,r\}$ on input $a$

First compute the NFA move on $a$:

• $\delta(p,a)=\{q\}$
• $\delta(q,a)=\{p\}$
• $\delta(r,a)=\{r\}$

So:

$$T_a=\bigcup_{s\in\{p,q,r\}}\delta(s,a)=\{q\}\cup\{p\}\cup\{r\}=\{p,q,r\}$$

Now take $\varepsilon$-closure:

$$\delta_{\text{DFA}}(\{p,q,r\},a) = \varepsilon\text{-closure}(\{p,q,r\})$$

Since $p$ and $r$ already have closure $\{p,q,r\}$ and $q$ closes to $\{q\}$, we get:

$$\varepsilon\text{-closure}(\{p,q,r\})=\{p,q,r\}$$

Therefore:

$$\delta_{\text{DFA}}(S_0,a)=\{p,q,r\}$$

---

From $S_0=\{p,q,r\}$ on input $b$

Compute NFA move on $b$:

• $\delta(p,b)=\{p,r\}$
• $\delta(q,b)=\emptyset$
• $\delta(r,b)=\{p\}$

So:

$$T_b=\bigcup_{s\in\{p,q,r\}}\delta(s,b)=\{p,r\}\cup\emptyset\cup\{p\}=\{p,r\}$$

Now take $\varepsilon$-closure:

We use set closure:

$$\varepsilon\text{-closure}(\{p,r\}) = \varepsilon\text{-closure}(p)\cup \varepsilon\text{-closure}(r) = \{p,q,r\}\cup\{p,q,r\} = \{p,q,r\}$$

Therefore:

$$\delta_{\text{DFA}}(S_0,b)=\{p,q,r\}$$

Result: The DFA transition table

We started from $S_0=\{p,q,r\}$. Both inputs loop back to the same subset, so the DFA has only one reachable DFA state:

$$S_0=\{p,q,r\}$$

Thus the DFA transition function is:

Accepting states (conditional)

Let $F_{\text{NFA}}$ be the set of accepting states of the $\varepsilon$-NFA. Then the accepting DFA states are:

• $S$ is accepting iff $S\cap F_{\text{NFA}}\neq\emptyset$
• (and if you treat acceptance as “some path accepts after $\varepsilon$-closure”, you can equivalently test $S$’s elements.)

Because the only DFA state is $S_0=\{p,q,r\}$, the DFA accepts all strings iff any of $\{p,q,r\}$ is accepting in the NFA; otherwise it accepts none.

Quick verification with a state-based view

Even without running more iterations:

• From $p$, an $\varepsilon$-move gets you to $r$.
• From $r$, an $\varepsilon$-move gets you to $p$ and $q$.
• From $q$, $\varepsilon$ does nothing.
• So as soon as you start, the $\varepsilon$-closure is already the full set $\{p,q,r\}$.
• On $a$ and $b$, the NFA transitions from states inside this full set always return you (after $\varepsilon$-closure) to the same full set.

Mermaid sketch of “closure collapse”: