2
$\begingroup$

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.

DFA-x refers to the DFA with more than one initial state

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.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ 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. $\endgroup$
    – Derek Elkins left SE
    Commented Oct 10, 2017 at 3:01
  • $\begingroup$ 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? $\endgroup$
    – Mr10k
    Commented Oct 10, 2017 at 6:27
  • 2
    $\begingroup$ @DerekElkins you should make it an answer. $\endgroup$
    – fade2black
    Commented Oct 10, 2017 at 6:46
  • $\begingroup$ 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. $\endgroup$
    – fade2black
    Commented Oct 10, 2017 at 6:55
  • $\begingroup$ Ah okay that makes sense, I just understood it in a different manner I think. Thanks for clearing that up for me! $\endgroup$
    – Mr10k
    Commented Oct 10, 2017 at 7:09

1 Answer 1

Reset to default
6
$\begingroup$

There are many ways of showing that DFAs with multiple initial states generate regular languages. Here are some:

  • 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.

NFAs with multiple initial states are in some sense more natural than NFAs with one initial state. Indeed, the power set construction, which constructs a DFA equivalent to a given NFA, works without any changes for this more general class of NFAs. Moreover, this more liberal definition allows you to prove that regular languages are closed under reversal by simply "reversing all arrows".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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