NFA for the star of a language (01 U 001 U 010)*

Question

Problem from page 5 of this pdf.

Give an NFA that recognizing the language (01 U 001 U 010)*

I think this is wrong because there should be an additional start state (accepting) going to state 1 for the empty string in the beginning. That's how the closure under star is proved in Sipser. Am I missing something?

Here's what I think it should be:

Answer 1

No, you correctly understood the star in the first pattern, but the NFA is correct. x* represents the pattern x repeated 0 or more times.

State 1 is the start state. You know it can match an empty string because the start state is also the end state. Another way you can think of it is that the arrow on the left indicates that there is an implicit start state which accepts an empty string and transitions to state 1.

Assuming I remember my classes correctly:

• The first arrow on the left indicates that when started you enter state 1.
• The double circle indicates that state 1 is also a valid end state.
• ε represents an empty string. This is part of what makes this finite automata non-deterministic. For example if you were in state 5, there is no one single correct response and a single string may be able to traverse more than one list of states.

Answer 2

It is generally a good practice to include a new start state as you mentioned but for this particular problem,it is unnecessary.A new start state is used to prevent the machine from producing unexpected strings since the initial start state may be pointed by arrows coming from non-accept states.But there is no such transition arrow in this particular example and introducing a new start state is unnecessary.