Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular

Question

Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$.

My thoughts: I understand that $L_2 = \{0^n1^n: n\geq 0\}$ can be shown to be not regular using the Pumping Lemma by starting with a string in $L_2$ of length at least the pumping length, and try to pump it outside the language.

So I've been trying, for $L_1$, to start with something and pump it to $L_2$, but I have been struggling to find a string such that all it's recompositions can be pumped into $L_2$. As it seems whether I can perform the pumping successfully always depends on the decomposition...

Could you please help? Thanks!

Answer 1

If $L_1$ was regular, then its complement, $L_2$, would be regular. This is a contradiction because you have shown that $L_2$ was not regular.