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$ Jul 16 at 18:00

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.