Show $\{0^1^|≠\}$ is not regular So I have the question: show &quot;Show $\{0^1^|≠\}$ is not regular&quot;. 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?
Try to express in natural language what $\overline{L}$ contains; that is, what words $L$ doesn't contain. Most obviously, it's &quot;words of the form $0^m0^n$, with $m = n$.&quot; However, it also contains &quot;words that are not of the form $0^m1^n$&quot;, such as &quot;$101010$&quot;. 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.