Construct a DFA with $\Sigma=\{0,1\}$ that accepts the language $\{ x \in \Sigma^* \mid x \notin L(0^*1^*) \}$

Question

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:

and this is the complement:

thanks

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.