NFA to DFA: Removing unnecessary states - What is NEW start state?

Question

I'm trying to understand the transformation scheme from NFA to DFA, and think I have grasped most of it (in terms of method).

The original NFA is the following:

And the DFA was constructed by:

However, the above example shows an NFA before unnecessary states have been removed, as well as after removal. Unnecessary referring to states with no incoming arrows.

QUESTION

How do you determine what the NEW initial state will be? I see that it is set to be {1,3}, but why?

Thanks in advance!

Could you give the original NFA? – J.-E. Pin Jun 02 '16 at 09:33 — J.-E. Pin, Jun 02 '16 at 09:33
@J.-E.Pin Updated in question :) – aprilrocks92 Jun 02 '16 at 09:45 — aprilrocks92, Jun 02 '16 at 09:45

score 2 · Accepted Answer · answered Jun 02 '16 at 10:06

The starting state of the DFA is the set of all states of the original NFA that can be reached from the starting state of the original NFA using only $\epsilon$-transitions. I.e., it is the set of all states that you could be in in the original NFA after reading the word $\epsilon$. Note that in general, the state of the DFA that you are in after reading the word $w$, is the set of states that you could be in in the original NFA after reading the word $w$.

For this particular case, that amounts to $\{1,3\}$.

Thanks a lot. This helped me a bunch. – aprilrocks92 Jun 02 '16 at 10:52 — aprilrocks92, Jun 02 '16 at 10:52

NFA to DFA: Removing unnecessary states - What is NEW start state?

1 Answers1

Linked