I want to show that this language is not context-free:
I struggle with the pumping lemma for CFL and i would like to know how to solve this problem. Thank you
(skipping the classic introductory text of the proof)
During my proof i chose the word $z = a^pb^pc^{p-1}$ ( correct me if this isn't a good choice)
The word z can be cut as $sv^iuw^it$
Let's take i = 2
From there i know that we have to explore all cases:
Case 1: v and w are only made of a's so we have $a^{p+|vw|}b^pc^{p-1}$ so this isn't in the language because $|vw| >= 1$
Case 2: it's the same thinking but v w are only made of b's
Case 3: v and w are only made of c's, if $i=2$ then we have $v^2$and $w^2$ so $|vw|=4$ so we have $a^pb^pc^{p-1+|vw|}$ = $a^pb^pc^{p-1+4}$ which mean here that it won't be in the language since we need $m>=n$
From there ( if everything yet makes sens) i am not too sure on how to continue this problem, could anyone help out ? Thanks a lot.
Best Answer
The tricky cases are when there is an $r\le\frac{p}2$ such that $v=a^r$ and $w=b^r$, because then if you make $i>1$, $sv^iuw^it$ is still in $L$. However, the pumping lemma says that $sv^iuw^it\in L$ for all $i\ge 0$, so you can pump down to $i=0$, so that $sv^iuw^it=a^{p-r}b^{p-r}c^{p-1}$. If $r>1$, this word is not in $L$, because $p-r<p-1$. Unfortunately, if $r=1$ the word is $a^{p-1}b^{p-1}c^{p-1}$, which is in $L$. The problem here is with your choice of $z$: you should have let $z=a^pb^pc^p$. This is in $L$, since the definition of $L$ requires only that $m\ge n$, not that $m>n$, and now everything works, both the cases that you’d already considered and the one that I just did.
The remaining possibilities are:
In every case, therefore, we can pump $z$ to get a word not in $L$, and the pumping lemma then implies that $L$ is not context free.