# formal languages – Show {0𝑚1𝑛|𝑚≠𝑛} is not regular

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.