I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \}$ is not regular.

This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p 2^p$. Consider any pumping decomposition $w = xyz$; $|y| > p$ and $|xy| \leq p$.

I'm not sure what to do next.

Am I on the right track? Or am I way off?

Thank you in advance.

  • $\begingroup$ You should be able to model your proof quite closely after the proof that $\{0^m1^m\}$ is not regular, with $01$ playing the role in your proof that $0$ plays in the original, and your $2$ playing the role of $1$. That will introduce a numerical factor of 2 at one point. $\endgroup$ – David Lewis Apr 4 '12 at 10:58

It’s fine to start with the word $w=(01)^p2^p$, where $p$ is the pumping length, but you’ve gone a bit astray after that. The pumping lemma tells you that $w$ has a decomposition $w=xyz$ such that $|y|\ge 1$, $|xy|\le p$, and for all $i\ge 0$, $xy^iz\in L$. In particular, $xz\in L$.

Since $|xy|\le p$, you know that $y$ is part of the first $p$ letters of $w$. The first $2p$ letters of $w$ are the alternating $0$’s and $1$’s, so $y$ cannot contain any $2$’s. In other words, $z$ includes $2^p$. Can $xz$ be in $L$? Remember, $y$ is not the empty string, so $xz\ne w$.

  • $\begingroup$ Thank you so much for your help. That makes sense. But how would I prove if xz is in L? $\endgroup$ – Momagic Apr 4 '12 at 6:03
  • $\begingroup$ @Momagic: You know that $xz$ contains all $p$ of the $2$’s in $w$; does it start with a string $(01)^p$, or with something else? $\endgroup$ – Brian M. Scott Apr 4 '12 at 6:11
  • $\begingroup$ I think it starts with a string (01)^p $\endgroup$ – Momagic Apr 4 '12 at 6:15
  • $\begingroup$ @Momagic: It does not. The $y$ part of the decomposition contains at least one symbol, and $|w|=3p$, so $|xz|\le 3p-1$. We already know that $z$ contains all $p$ of the $2$’s in $w$; when you drop them off the end of $xz$, what’s left can have at most $2p-1$ symbols, so it cannot possibly be $(01)^p$. $\endgroup$ – Brian M. Scott Apr 4 '12 at 6:21
  • $\begingroup$ Oh I see now. Thank you! $\endgroup$ – Momagic Apr 4 '12 at 6:38

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.