Converting this NFA-e to DFA

Question

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?

Answer 1

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:

I learned this here http://www.cs.um.edu.mt/gordon.pace/Research/Software/Relic/Transformations/FSA/remove-unreachable.html