# Converting this NFA-e to DFA

I came across this question about NFA-e and thought to convert it into DFA:

This is what I did.

$$\begin{array}{|c|c|} \hline & a \\ \hline q_1&q_2 \\ \hline q_2&\phi \\ \hline q_3&\phi \\ \hline \end{array}$$

Found epsilon closure of states:

$$\varepsilon(q_1) = q_1$$

$$\varepsilon(q_2) = [q_2, q_3, q_1] = P$$ (let)

$$\varepsilon(q_3) = [q_3, q_1] = Q$$ (let)

Defined new transition rule for the states:

$$\delta'(q_1, a) = \varepsilon\{\delta(q_1, a)\} = \varepsilon(q_2) = P$$

$$\delta'(P, a) = \varepsilon\{\delta(q_2, a) \cup\delta(q_3, a) \cup \delta(q_1,a)\}=\varepsilon\{\phi\ \cup\ \phi\ \cup q_2\}=P$$

$$\delta'(Q,a)=\varepsilon\{\delta(q_3,a) \cup \delta(q_1,a)\}=\varepsilon\{\phi \cup q_2\}=P$$

$$\begin{array}{|r|r|} \hline &a\\\hline q_1&P\\\hline *P&P\\\hline Q&P\\\hline \end{array}$$

Now I'm stuck on how to make the FSM. There is no transition to $$Q$$ from $$q_1$$ or $$P$$. What did I do wrong?

• It looks like you already have the FSM. It is $\langle \{a\}, \{q_1, P, Q\}, q_1, \delta, \{ P \} \rangle$, where $\delta : \{q_1, P, Q\} \times \{a\} \to \{q_1, P, Q\}$ is identically equal to $P$. Why would you want a transition to $Q$? (Notice that this FSM can be minimized by removing $Q$) Mar 29 '20 at 22:39
• @Steven thanks. I did not know of removing unreachable states in DFA, which is covered here: cs.um.edu.mt/gordon.pace/Research/Software/Relic/…. Apr 6 '20 at 10:19

Alright we've to remove the unreachable state that is $$Q$$, for which we have to follow these steps:

1. Initialize a set $$R$$ containing the initial state.
2. Create a set $$M$$ which'll contain the states which are reachable from states in $$R$$ in single transition.
3. Perform $$R = R\cup M$$.
4. Repeat from step 2 until $$R$$ stops getting new states.
5. Remove states from complement of $$R$$.

Create set $$R = \{q_1\}$$.

Calculate $$M$$ by finding states which can be reached from $$\{q_1\} = \{P\}$$.

Perform $$R = R\cup M:\{q_1\}\cup\{P\}=\{q_1, P\}$$.

Calculate $$M$$ again from $$\{q_1,P\}=\{P\}$$.

Perform $$R=R\cup M:\{q_1,P\}\cup\{P\}=\{q_1,P\}$$. $$R$$ has no new states to add. Therefore, we'll remove states from complement of $$R: \{q_1, P, Q\} - \{q_1,P\}=\{Q\}$$. The FSM will be: