Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – 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$.

share|cite|improve this answer
Thank you so much for your help. That makes sense. But how would I prove if xz is in L? – Momagic Apr 4 '12 at 6:03
@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? – Brian M. Scott Apr 4 '12 at 6:11
I think it starts with a string (01)^p – Momagic Apr 4 '12 at 6:15
@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$. – Brian M. Scott Apr 4 '12 at 6:21
Oh I see now. Thank you! – Momagic Apr 4 '12 at 6:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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