NFAs with more than one initial state

Problem Detail: 

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.

Asked By : nubz0r

Answered By : Yuval Filmus

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 $\epsilon$ transitions.

For example, here is an NFA which accepts the language of all words not containing all letters in the alphabet $\Sigma$. For each $\sigma \in \Sigma$ there is a state $s_\sigma$. For each $\tau \neq \sigma$, there is a self-loop labelled $\tau$ around $s_\sigma$. All $s_\sigma$ are starting states as well as accepting states. The state $s_\sigma$ is supposed to represent all words not containing $\sigma$.

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_\sigma$ with $\epsilon$ transitions. The semantics of both NFAs are exactly the same.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24491