1
$\begingroup$

$$ 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?

$\endgroup$
1
$\begingroup$

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.

But what about this case:

$$ 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 $$

You have to show that for every possible splitting of the string to be pumped, where the constraints hold, for some i, the string does not belong to the language.

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – G. Bach Oct 16 '13 at 0:15
  • $\begingroup$ Yes, you are right, my fault. I was very tired when I wrote my answer :) $\endgroup$ – mrjasmin Oct 16 '13 at 1:03
1
$\begingroup$

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.

$\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.