1
$\begingroup$

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

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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$) $\endgroup$
    – Steven
    Mar 29 '20 at 22:39
  • $\begingroup$ @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/…. $\endgroup$
    – Adnan
    Apr 6 '20 at 10:19
0
$\begingroup$

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:enter image description here

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.