7
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Please excuse the long hiatus, but google coughed up this thread regarding a related question I'm looking for. Pretty much same question regarding dfa's, but instead on input that's just a string, call it $\vec\sigma\in\Sigma^\ast$, let the input be $(s_0,\vec\sigma)\in S\times\Sigma^\ast$, i.e., you give it initial state $s_0\in S$ too. Can that also be converted to a single-starting-state dfa??? I'd think each possible $s_0\in S$ defines a different language accepted by the dfa, call it $L_{s_0}$. But $S$ may be partitioned into equivalence classes where states in a class accept the same $L$ $\endgroup$ – John Forkosh Aug 11 '16 at 7:56
  • $\begingroup$ If you have a question, please ask it on the site. Comments are for commenting on answers. $\endgroup$ – Yuval Filmus Aug 11 '16 at 7:59
  • $\begingroup$ Okay, I'll reformat. Sorry for the inconvenience. $\endgroup$ – John Forkosh Aug 11 '16 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.