# Epsilon transition in NFA to DFA conversion

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$$.

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.

• 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) – Jac Frall Apr 28 at 12:13
• 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. – Jac Frall Apr 28 at 12:23
• @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$. – frabala Apr 28 at 12:31
• 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. – frabala Apr 28 at 12:41
• No this is a book written by my professor – Jac Frall Apr 28 at 12:42