# Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular

I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \mid m \ge0\}$ 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$ such that $|y| >0$ and $|xy| \le p$.

I'm not sure what to do next.

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

• you're on the right track. if you "pump" you change the number of 0's and 1's, but not the number of 2's (why?). This will lead a contradiction. – Ran G. Apr 4 '12 at 6:50
• oh, note that it can't be that $|y|>p$ and $|xy|<p$. I guess this is a typo and you meant $|y|>0$. – Ran G. Apr 4 '12 at 6:52
• Note that Pumping lemma is not the fastest way here, as $L$ is very close to canonical examples for non-regular languages. Try to use closure properties of $\mathrm{REG}$! – Raphael Apr 4 '12 at 10:24
• Or check the proof of the pumping lemma to realize you can have the pumped string near the end too, and pump the 2s, which is easier. – vonbrand Nov 17 '15 at 13:42
• @vonbrand or take the reverse of the language and apply the straight pumping lemma to that one. – Al.G. Apr 1 '19 at 22:13

Hint: You need to consider what all the decompositions $w=xyz$ look like, so what are all the possible things $x$, $y$ and $z$ can be given that $xyz=(01)^p2^p$. Then you pump each one and see whether you get a contradiction, which will be a word not in your language. Each case needs to lead to a contradiction, which would then be a contradiction of the pumping lemma. Voila! The language would not be regular.

Of course, you need to work through the details and consider all the possible splittings.

You have a decomposition $xyz = (01)^p 2^p$ and a length constraint $|xy| \le p$. What does this say about how $x$, $y$ and $z$ can fit in the decomposition? In particular, the pumping lemma allows you to repeat $y$, so your objective is to find some way in which repeating $y$ many times (or removing $y$, sometimes this is simpler) will irremediably perturbate the pattern that defines the language.

There's an obvious boundary in the pattern: the first part contains repetitions of $01$, the second part contains only $2$'s. The interesting thing is where $y$ falls down. Is $y$ always contained in one of these parts, or can it straddle the two?

Since $|xy| \le p$, $xy$ is entirely contained in the $(01)^p$ part, and $z$ contains all the $2$'s. So if you repeat $y$ one more time, you get a longer first part, but the $2^p$ part remains the same. I other words, $xyyz$ ends with exactly $p$ letters $2$. To finish the proof properly, show that $xyyz$ contains too many letters $0$ and $1$ to fit the regular expression.

Three years later we are going to prove that $L = \{(01)^m 2^m \mid m \ge0\}$ with $\Delta=\{0,1,2\}$ is not regular by contradiction using closure properties(a faster way than using the pumping lemma).

First we suppose that $L$ is regular. We know that regular languages are closed under inverse homomorphism.

Consider the homomorphism $h:\Sigma^* \rightarrow \Delta^*$ with:

$\Sigma = \{a,b\}$

$h(a)= 01$

$h(b)= 2$

The inverse homomorphism of $L$ is:

$h^{-1}(L)= \{a^nb^n| n\geq 0 \} = L'$

This generate a contradiction because $L'$ is a canonical example of an irregular language so $L$ can't be regular.

I am going to give a non-answer to this question, since this isn't exactly the pumping lemma, but maybe sheds light on what the idea of the pumping lemma is. Here is a basic fact about deterministic finite state automata, which is the essence of the Myhill-Nerode theorem: If two strings $a$ and $b$ drive the FSA to the same state, then for any $c$, either both of $ac$ and $bc$ are accepted, or neither is.

Back to your problem, suppose that a deterministic automaton for you language has $n$ states. Then at least two of $(01)^1$, $(01)^2$, $\ldots$, $(01)^{n+1}$, say $(01)^p$ and $(01)^q$ with $p\neq q$, drive the automaton to the same state (this is the pigeon-hole principle). According to the fact, then either both of $(01)^p2^p$ and $(01)^q2^p$ are in $L$ or neither is, which is a contradiciton.