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