2
$\begingroup$

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.

  • 0
    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.2012-04-04

1 Answers 1

1

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

  • 0
    Thank you so much for your help. That makes sense. But how would I prove if xz is in L?2012-04-04
  • 0
    @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?2012-04-04
  • 0
    I think it starts with a string (01)^p2012-04-04
  • 0
    @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$.2012-04-04
  • 0
    Oh I see now. Thank you!2012-04-04