0
$\begingroup$

enter image description here

enter image description here

I worked through this conversion and it all makes sense except for one small part. Shouldn't $(q_1q_2)$ go to $q_1$ in the DFA on input $0$, not a self loop?

We have state $q_iq_2$ to begin with because $q_0$ goes to $q_1$ and $q_2$ on a $1$.

Then trying to figure out what states $(q_1q_2)$ goes to:

On a $0$ $(q_1q_2)$ goes to $q_1$ because in the original NFA $q_1$ goes to $q_1$ and $q_2$ goes to the empty set. On a $1$ $(q_1q_2)$ goes to $q_3$ because in the original NFA $q_1$ goes to $q_3$ and $q_2$ goes to the $q_3$.

$\endgroup$
1
$\begingroup$

If I'm not mistaken, the technique is: for each transition $q \to^a Q'$ of the NFA (NFA transitions are from states to sets of states), you take $$q \to^a \text{state}\big(Q'\cup\{q'' ~|~q'\in Q'~\text{and}~q'\to^\epsilon Q''~\text{and}~q''\in Q''\}\big)$$

This is just a formal way to say "in $q\to^a Q'$, take into account also the $\epsilon$-transitions from $Q'$".

Here, it's $q_1 \to^0\{q_1\}$. Therefore, this results to $q_1 \to^0 \text{state}\big(\{q_1\}\cup\{q_2\}\big) = (q_1, q_2)$.

The function "state" is just to map a set of states of the initial NFA to the corresponding state of the DFA.

$\endgroup$
  • $\begingroup$ I was told by my professor that after the input is consumed, the state stops. That is, once the input 0 is consumed it cannot move further even if there are epsilon transitions. (I also updated the question to make it more specific) $\endgroup$ – Jac Frall Apr 28 at 12:13
  • $\begingroup$ It sounded like my professor meant you can consume them before the input is accepted but not after. However doesnt this contradict with what the textbook shows. $\endgroup$ – Jac Frall Apr 28 at 12:23
  • $\begingroup$ @JacFrall Indeed it contradicts the pictures, so at this point I'm not sure what your professor meant. Note that the same happens with transition $q_3 \to^1 q_4$. $\endgroup$ – frabala Apr 28 at 12:31
  • $\begingroup$ Is this from Sipser's book? If yes, then indeed $\epsilon$-transitions are taken into account in the end. You're missing that extra step ($E(R)$, where $R\subseteq Q$). That's the final transition function. $\endgroup$ – frabala Apr 28 at 12:41
  • $\begingroup$ No this is a book written by my professor $\endgroup$ – Jac Frall Apr 28 at 12:42

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.