Using pumping lemma to prove that $L = \{(01)^m 2^m \}$ is not regular?

Question

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.

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