18
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ran G. Apr 4 '12 at 6:50
  • $\begingroup$ oh, note that it can't be that $|y|>p$ and $|xy|<p$. I guess this is a typo and you meant $|y|>0$. $\endgroup$ – Ran G. Apr 4 '12 at 6:52
  • 1
    $\begingroup$ 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}$! $\endgroup$ – Raphael Apr 4 '12 at 10:24
  • 1
    $\begingroup$ 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. $\endgroup$ – vonbrand Nov 17 '15 at 13:42
  • $\begingroup$ @vonbrand or take the reverse of the language and apply the straight pumping lemma to that one. $\endgroup$ – Al.G. Apr 1 at 22:13
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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