3
$\begingroup$

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 ?

3 Answers 3

6

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.

2

Yes, it is almost that easy. The main idea behind the pumping lemma is this:

  • Let us assume that we have an automaton with $n$ states.
  • Fix word $w$.
  • For any subsequence of letters of $w$ that has lenght greater than $n$, you had to pass through some state more than once ($n$ states and at least $n+1$ letters).
  • If you have visited some state more than once, there is a loop, and so, it is possible to go through this loop again (and pump the word up).

In your example, if the automaton had $n$ states, and you have choosen $w = a^{n+1}b^{n+1+k}c^{k}$, then during the parse of $a^{n+1}$ some state happened at least twice. Let's assume it was after $4$-th and after $10$-th letter $a$ (you have no control over where the repetition will be, it depends on the automaton). Then you can copy-paste the subword from the $4$-th to the $10$-th letter. So if the automaton were to accept $a^{n+1}b^{n+1+k}c^{k}$, is bound to accept $a^{10}(a^6)^ma^{n-9}b^{n+1+k}c^{k}$ for any $m$.

Hope that helps ;-)

2

In order to use the Pumping Lemma to prove that a language is not regular you need to show that no pumping constant exists. That means that you will have to do with an arbitrary length $n$ and show it will not work by using a cleverly chosen word.

In your example language you have made it difficult for yourself by taking a word with two variables. Simply $a^nb^{2n}c^n$ will do, well, in this case. It is in the language and is longer than $n$.

Your argument is not completely OK. You cannot choose $uv=a^n$ as we only know that $|uv|\le n$. But we do know $v$ consists of only $a$'s and if there $s$ of them $uv^2w$ will indeed be of the form $a^{n+s}b^{2n}c^n$ which is outside the language. It is that easy.

Then your example language is even non-context-free. That property can be attacked using the related pumping lemma for context-free languages. Which is slightly more complicated as it involves a decomposition into five parts, and more importantly, we do not know that the pumping part is near the beginning of the word. Usually there are much more cases to consider.