Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular (without using complement closure)

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\}$ (without using the complement closure property).

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

Suppose towards a contradiction that $L_1$ is regular and let $p$ be its pumping length.

Since $0^{p}1^{p+p!} \in L$ there must be some $1 \le k \le p$ such that $0^{p+ik} 1^{p + p!} \in L_1$ for every integer $i \ge -1$.

Choosing $i=\frac{p!}{k}$ (this is an integer since $k$ is a factor of $p!$) yields the following contradiction: $$ 0^{p+\frac{p!}{k} \cdot k} 1^{p + p!} = 0^{p + p!} 1^{p + p!} \in L_1. $$