# Pumping Lemma problem

Apply pumping lemma to each of these and prove that they are not regular.

$L = \{ (0^p)(1^q)2 \mid 0 < q < p\}$

$L_2 = \{ (a^p)(b^q)(c^r) \mid p = q \text{ or } q = r\}$

Here my bad attempt at $L$.

Proof: Assume $L$ is regular let $m$ be the number from the pumping lemma.

Let $w = 0^m 1^m 2$ this is clearly in $L$.

By the pumping theorem there exist words $w_1$, $w_2$, $w_3$ such that $w = w_1w_2w_3, |w_2|>0, |w_1w_2| \le m$.

This how far I got; it's not very far but the text is far from clear how to do this.

• What does the pumping lemma have to say further? Apr 3 '13 at 7:49
• You mean if I was to keep following my attempt? To be honest the Linz book that I am using makes it into a sort of game. Which makes it sort of hard to follow. My finished attempt would include (for all symbol)i such that (Natural numbers) w1*w2*w3 exist in L. So w2^l = a for some l exist in Natural numbers. With this it is easy however to pick an i such that w1*w2^i *w3 = 0^m * 1^m * 2 does not exist in L Apr 3 '13 at 7:54
• The "formal statement" on Wikipedia is what you're talking about when you mean the pumping lemma, right? Apr 3 '13 at 8:15
• But if we let $w = 0^m1^{m-1}2$ with $m$ from the pumping lemma, then $w_1w_2$ as in pumping lemma consists of only zeroes. Hence $w_1w_3 = 0^k1^{m-1}2$ with $k < m$, hence not in $L$. Apr 3 '13 at 8:42
• @Lord_Farin: Yet another proof of my own illiteracy. ;-) Apr 3 '13 at 8:46

A fairly complete proof that the first language is not regular.

If it were regular, then by the Pumping Lemma let $p$ be a pumping length for the language. Consider the string $w = \mathtt{0}^p\mathtt{1}^{p-1}\mathtt{2} \in L$. Since $|w| = p + (p-1)+ 1 = 2p \geq p$, by the Pumping Lemma $w$ may be written as $x y z$ where

• $| x y | \leq p$;
• $| y | > 0$; and
• $x y^n z \in L$ for all $n \geq 0$.

Since $| x y | \leq p$, and $xy$ is an initial segment of $w$, it follows that $xy$ must consist entirely of $\mathtt{0}$s, so in particular $x = \mathtt{0}^i$ and $y = \mathtt{0}^j$ for $i,j$ with $i + j \leq p$ and $j > 0$. It also follows that $z = \mathtt{0}^{p-i-j} \mathtt{1}^{p-1} \mathtt{2}$. Note that $x y^0 z \in L$, however $$x y^0 z = xz = \mathtt{0}^i \mathtt{0}^{p-i-j} \mathtt{1}^{p-1} \mathtt{2} = \mathtt{0}^{p-j} \mathtt{1}^{p-1} \mathtt{2},$$ and $p-j \leq p-1$, contradicting that $x y^n z$ belongs to $L$!

The second language can be shown to be non-regular by assuming $p > 1$ is a pumping length for it. (Note that if $p$ is a pumping length for a language $L$ then every $p^\prime > p$ is also a pumping length for $L$, so the assumption $p > 1$ won't affect whether the language satisfies the conclusion of the Pumping Lemma.) Now look at the string $w = \mathtt{a}^p \mathtt{b}^p \mathtt{c}$.

• Replacing $p$ by $p+1$ in both arguments will avoid the $p > 1$ condition. Apr 3 '13 at 9:21
• @Lord_Farin: I thought of that, but decided on this formulation. I'm still not certain which is better, though I think I will at least add a small note. Apr 3 '13 at 9:25