0
$\begingroup$

So I have the question: show "Show $\{0^𝑚1^𝑛|𝑚≠𝑛\}$ is not regular". I've already seen various proofs for this question, but they all have one step I don't get.

They all take: $\bar{L}∩(0^∗1^∗)$ ($\bar{L}$ is the complement of $L$) and show that it's not regular. I don't get why we can't just take $\bar{L}$. Because isn't $\bar{L} = \{0^𝑚1^𝑛|m=n\}$ which is the same as $\{0^n1^n|n ≥ 0\}$ which we know is not regular? What am I missing?

$\endgroup$
4
$\begingroup$

Try to express in natural language what $\overline{L}$ contains; that is, what words $L$ doesn't contain. Most obviously, it's "words of the form $0^m0^n$, with $m = n$." However, it also contains "words that are not of the form $0^m1^n$", such as "$101010$". That's why the intersection with $0^*1^*$ is employed, to not bother with these words.

The demonstration is then possible because intersection and complementation are closed properties on the regular language. So if $\overline{L} \cap L(0^*1^*)$ is not regular, we know that $\overline{L}$ must not be regular, so its complement, $L$, must not be regular.

$\endgroup$
0
$\begingroup$

Assume m ≠ m'. After processing $0^m$ and $0^{m'}$ you cant be in the same state, because in one state adding $1^m$ is not accepted and in the other state adding $1^m$ is accepted. Since is the case for all m ≠ m', the number of states is not finite.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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