[Solved]: Is this pumping lemma proof correct?

Problem Detail: 

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

Asked By : redundant6939

Answered By : mrjasmin

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16114

 Ask a Question

 Download Related Notes/Documents