Search code examples
automatadfanfa

How many initial states can an NFA and DFA have?


How many initial states can an NFA and DFA have in Finite Automata theory


Solution

  • It depends on your definitions. That said, it's hard to imagine any reasonable definition of a DFA in which there is more than one initial state. Why? Well, you'd need a way of telling which state to start in. Typically, only the input string is available to a DFA, and that could be empty. It's easier to imagine an NFA being defined in such a way that multiple initial states are OK. It would be basically equivalent to having a separate initial state with epsilon-transitions to the multiple initial states, and then just simply not showing the "true" initial state. This would be analogous to the way NFAs need not show dead states and can simply crash.