0
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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. $$

$\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.