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

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

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Many thanks for your answer! Actually I noticed that too, but I was wondering specifically how to "use the pumping lemma" to prove it, if possible : ) $\endgroup$ Commented Jul 16, 2022 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.