# Prove that a language is regular if it is accepted by a DFA with more than one intial state

So I'm currently studying theory of computation, and I was wondering if you could theoretically have more than one initial state in a DFA and if you can prove that a DFA with more than one initial state can depict a regular language? So essentially, can we prove that a language is regular if and only if it is accepted by a DFA with more than one initial state?

I was experimenting with the language L which consists of all strings over the alphabet {a,b} which contains an even number of a's.

I managed to draw a DFA for this language as well as my representation for a DFA with more than one initial state. From the looks of things, it makes sense.

But is there any way that we can PROVE that a language is regular if it is accepted by a DFA with more than one state? So for any given DFA with more than one initial state, are the languages that it accepts is regular? If so, how can I prove it? I know from Kleene's Theorem that a regular language is accepted by an FA, but from the research I have done I have not been able to find anything regarding my question.

• NFAs with $\varepsilon$ transitions are equivalent to DFAs. A DFA with multiple initial states can be modeled as an $\varepsilon$-NFA that's the same except that it has one additional state, which is the sole initial state, with an $\varepsilon$-transition to each state that is an initial state in the original DFA. – Derek Elkins Oct 10 '17 at 3:01
• To my understanding, this is still different to the question I was asking. I am more interested in knowing if we can prove that a language is regular if it is accepted by a DFA with more than one initial state. Wrt NFA's with ε-transitions, this isn't really working with more than one initial state is it? It's more a sole initial state being used to give more than one input? – Mr10k Oct 10 '17 at 6:27
• @DerekElkins you should make it an answer. – fade2black Oct 10 '17 at 6:46
• The standard definition of DFA assumes a single state $q_0 \in Q$ as the initial state. Of course you can generalize this definition by introducing more than one initial state. But as @DerekElkins suggests you can easily transform it into a NFA (and then into DFA) with a single initial state meaning that a language is regular if it is accepted by a DFA with more than one initial state. – fade2black Oct 10 '17 at 6:55
• Ah okay that makes sense, I just understood it in a different manner I think. Thanks for clearing that up for me! – Mr10k Oct 10 '17 at 7:09

• You can prove using Nerode's theorem that for any DFA, the set of words taking the DFA from state $q_1$ to state $q_2$ is regular.
• Using "dynamic programming", you can construct a regular expression for the set of all words taking a DFA from state $q_1$ to state $q_2$.
• Using $\epsilon$ transitions from a new initial state, you can construct an NFA equivalent to your DFA.