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
