Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer

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 ;-)

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.