# Is this pumping lemma proof correct?

$$L = \{a^ib^jc^k \mid i,j,k > 0 \text{ and } i+k>j\}$$

I say it's not regular. Proof by pumping lemma: Find a string $xy^iz$ that is not in $L$ (respecting the constraints). Let $w=x^py^pz^p$.

Let $i=2$. $x^p(y^py^p)z^p$ is not in $L$.

Thus $L$ is not regular.

Is this proof correct?

The proof is not correct nor complete. You have to show that for every possible splitting of the string to be pumped, where the constraints of the lemma hold, the pumped string does not belong to the language.

You have only showed for one case that the string does not belong to the language and hence that the language is not regular.

$$z = x^py^pz^p, take \ i = 0 \ , uv = x^p, \ then \ z = uv^0w \ does \ not \ belong \ to \ the \ language, \ the \ condition \ i+ k > j \ is \ violated$$
• "for every possible splitting" - this sounds misleading to me. Every word of length at least $p$ must have some splitting satisfying those three well-known conditions, but not every splitting with valid $uv$ needs to be pumpable. – G. Bach Oct 16 '13 at 0:15
Here is a different proof. Suppose $L$ was context-free. Then so would be $L_1 = \{ a^i b^j : i > j > 0 \}$, hence so would be $L_2 = L_1 b + a^* ab + a^* = \{ a^i b^j : i \geq j \geq 0 \}$. Reversing $L_2$ and switching $a$ and $b$, we would also have $L_3 = \{ a^i b^j : j \geq i \geq 0 \}$ regular. So the intersection $L_2 \cap L_3 = \{ a^n b^n : n \geq 0 \}$ would be regular, which was probably shown in class to be false.