I have a few questions about Pumping Lemma Contrapositive.
First of all, how do I choose pumping length $n$? Is it just any constant from the language definition? i.e. I have $L=\{a^kb^gc^hd^j\}$ so I can choose any constant from set $k, g, h ,j$ since those are 'pumping' a length of word?
Secondly, lets say I have language defined as follows:
$L=\{a^ib^jc^k : i,j,k >0 \land i+k\leq j\}$
What I understand, I have to make word definition which length will be greater or equal to chosen parameter $n$ so:
$z=a^nb^{n+k}c^k$
Then I have to do a split into $uvw$ which satisfies conditions: $|uv|\leq n$ and $|v|\geq 1$ so:
$uv=a^n$
$u=a^s \land v=a^{n-s}$ so my word looks as follows $a^sa^{n-s}b^{n+k}c^k$ and I have to find such $i$ so word $uv^iw$ is not in the language.
For $i = 2$ I have equation:
$s+2n-2s+k \leq n+k$
$2n-s+k \leq n+k$ and since $s\lt n$ then this word will not be in the language -> L is not regular.
Is it that easy? Or is there something I misunderstood ?
Best Answer
You don’t choose the pumping length: the lemma says that if the language is regular, there is a pumping length, but it doesn’t say what that length is. Thus, when you’re using the pumping lemma to prove that a language $L$ is not regular, you can only assume that there is a pumping length $n$; you can’t assume that it’s related to the definition of the language in any particular way.
In the case of the language $$L=\left\{a^ib^jc^k:i,j,k>0\text{ and }i+k\le j\right\}\;,$$ for instance, you assume that $L$ is regular and let $n$ be the pumping length, whatever that may be. Then you know that $|a^nb^{n+1}c|\ge n$, so you know that it can be decomposed as $uvw$ with $|uv|\le n$ and $|v|\ge 1$ in such a way that $uv^mw\in L$ for all $m\ge 0$. (I used $k=1$ because there’s no need to complicate matters even a little by considering a general $k\ge 1$.)
Your next step isn’t quite right: you don’t know that $|uv|=n$, but only that $|uv|\le n$, so you know that $uv=a^\ell$ for some $\ell\le n$. Thus, $v=a^r$ for some $r\ge 1$, and therefore $u=a^{\ell-r}$, so your word is
$$\underbrace{a^{\ell-r}}_u\underbrace{a^r}_v\underbrace{a^{n-\ell}b^{n+1}c}_w\;.$$
Finally, for each $m\ge 0$ you have
$$uv^mw=a^{\ell-r}a^{mr}a^{n-\ell}b^{n+1}c=a^{n+(m-1)r}b^{n+1}c\;,$$
and since $n+(m-1)r+1\le n+1$ iff $m\le 1$, it’s clear that $uv^mw\notin L$ whenever $m\ge 2$.
In other words, your proof is correct apart from the small technical error of assuming that $|uv|=n$, and yes, it is that easy.