Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
