I am trying to construct a DFA with $\Sigma=\{0,1\}$ that accepts the language $\{ x \in \Sigma^* \mid x \notin \mathcal{L}(0^*1^*) \}$. To do this I first tried constructing a DFA that accepts $x \in \mathcal{L}(0^*1^*)$ and then found the complement of that DFA by switching the accept states and non accept states. But the quiz marked this incorrect saying that the string '' should not be accepted?

This is my first DFA:

enter image description here

and this is the complement:

enter image description here


  • $\begingroup$ What is your question? The empty string is in $L(0^*1^*)$, consequently not in its complement, your "complement" accepts it. $\endgroup$
    – greybeard
    Mar 21, 2022 at 7:46

1 Answer 1


The language $$ L = (0^*1^*) $$ is such that the empty string $\epsilon \in L$. We can see $L$ as the language composed of strings of any number of $0$ followed by any number of $1$. One DFA recognizing this language is composed of an initial and accepting state $q_0$ with a self loop for the symbol $0$ and a transition to a new state $q_1$ for the symbol $1$; the state $q_1$ is accepting as well and also has a self loop for the symbol $1$.

What we know about $L^c$ is that:

  1. it does not contain $\epsilon$, and
  2. it does not contain strings composed only of any number of $0$ followed by any number of $1$.

That is, we want to read at least one symbol. So, first of all, if we start reading a sequence of $1$, we want to see at least one $0$, and at that point we can see any sequence of $0$ and $1$ and we will accept the string. If the string to recognize begins with a sequence of $0$, we need to see at least one $1$, then at least one $0$, then we'll accept any sequence of symbols.

This may be enough to solve the problem, but to do it with the "DFA-inversion" construction, try to think about your transition function $\delta$: is it total? That is, we have transitions defined from every state for every symbol? Or some are left implicit?

I think this "hints" are enough to think about your exercise in a different way, but if you have doubts comment for more details.


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.