1

Question 4 asks to convert this NFA to a DFA:

Q4 asks to convert this NFA to a DFA

The solution is as follows:

Solutions' DFA

Whereas I found this as a solution (excuse the messy layout):

My DFA (excuse the messy layout)

My DFA is identical to the solutions' except the initial state (underlined).

The solutions omitted the 0 state (NFA initial state) and made 1,3 the DFA initial state (mine stays 0).

Can anybody please explain why they removed the 0 state and made 1,3 initial instead?

Edit: the original Q has been answered, but the following NFA to DFA doesn't seem to follow:

enter image description here

The DFA -

I've changed the labels for comprehension: enter image description here

But shouldn't the new initial state be 1,4 (not in DFA)?

Kit oh
  • 41
  • 4

1 Answers1

3

Okay I stumbled on another thread that explains it well: https://math.stackexchange.com/questions/1809453/nfa-to-dfa-removing-unnecessary-states-what-is-new-start-state#:~:text=1%20Answer&text=The%20starting%20state%20of%20the,after%20reading%20the%20word%20%CF%B5.

Basically, the new DFA's initial state is the set of all states the NFA's initial state reached using only epsilon transitions.

Kit oh
  • 41
  • 4
  • Exactly: for all practical purposes the NFA has two initial states. – Brian M. Scott Dec 11 '20 at 02:15
  • This Q removes the original initial state, but a Q in this same tut kept the original initial state and didn't include the new initial state (this new state wasn't in the DFA at all). So which do you choose when drawing the DFA? @Brian M. Scott – Kit oh Dec 11 '20 at 04:04
  • I’d have to see the other example. – Brian M. Scott Dec 11 '20 at 04:07
  • I edited in the other example @Brian M. Scott – Kit oh Dec 11 '20 at 04:29
  • It doesn’t really matter whether you label it $0$ or $1,4$: it’s the transitions that are important. Labelling it $1,4$ is thinking of the NFA as having two initial states and ignoring its state $0$; labelling it $0$ is treating it the same way but giving it the label of the original initial state. I prefer the $1,4$ label, but that’s mostly a matter of taste. – Brian M. Scott Dec 11 '20 at 04:42
  • Thanks for the input Brian – Kit oh Dec 11 '20 at 05:02
  • My pleasure. $ $ – Brian M. Scott Dec 11 '20 at 05:12