So I can take a given NFA with a single start state and convert it into an equivalent DFA quite easily, however I'm stumped when it comes to an NFA with multiple start states.
Since a DFA can only have one start state (if I'm correct) how do I know which of the two start states in the NFA becomes the sole start state in the DFA.
For reference, this is the NFA I'm trying to convert:
N| a | b | c |
____________________________
->0| {0,2} | {0,3} | --- |
*->0| {0} | {0} | {3} |
0| {2} | --- | {2,3} |
* 0| {2} | --- | {3} |
Where: -> = initial state, * = accepting state, --- = empty set,
A NFA with multiple start states is equivalent to a NFA with an additional state (which becomes the new, single start state) and ϵ-edges from that to the "actual" start states:
N| a | b | c | ϵ |
----+-------+-------+-------+-------+
0| {0,2} | {0,3} | {} | {} |
* 1| {0} | {0} | {3} | {} |
2| {2} | {} | {2,3} | {} |
* 3| {2} | {} | {3} | {} |
->4| {} | {} | {} | {0,1} |