I\'m trying to give a meaningful definition for NFAs with more than one initial
ID: 652135 • Letter: I
Question
I'm trying to give a meaningful definition for NFAs with more than one initial state. I know from the formal definition in Wikipedia that it is possible to have more than one initial state, it mentions that "There is an easy construction that translates a NFA with multiple initial states to a NFA with single initial state, which provides a convenient notation."
I believe the power set construction could help me on this matter but I'm having a hard time understanding it. It could probably be modified so that it can be applied into the definition I want to give, but i don't know how.
I would appreciate any help I can get on this matter.
Explanation / Answer
An NFA with multiple starting states makes a non-deterministic choice of the starting state, in the same way that it makes non-deterministic choices throughout its operation. It is equivalent to an NFA with a single new starting state connected to the former starting states with ? transitions.
For example, here is an NFA which accepts the language of all words not containing all letters in the alphabet ?. For each ??? there is a state s?. For each ???, there is a self-loop labelled ? around s?. All s? are starting states as well as accepting states. The state s? is supposed to represent all words not containing ?.
In order to convert this to an NFA with a single starting state, add a new state s which is the new starting state, and connect s to all s? with ? transitions. The semantics of both NFAs are exactly the same.