# Minimum pumping length of a context-free language

I was studying about the minimum pumping length of the language $$L$$ containing all palindromes over $$\{a,b\}$$ from this material about the pumping Lemma for CFLs.

The productions are as follows:

$$S\to aSa \mid bSb \mid a \mid b \mid \lambda$$

We have two cases to deal with,

• when the string $$w\in L$$ is of sufficient length and |$$w$$| is even,

the string is either of the form $$w=uaau^R$$ or $$ubbu^R$$.

I understood the explanation and why the minimum pumping length is 3.

• when the string $$w\in L$$ is of sufficient length and |$$w$$| is odd, there may be four possibilities,

$$uaaau^R$$ $$uabau^R$$ $$ubbbu^R$$ $$ubabu^R$$

I didn't understand the explanation given which goes like:

I didn't get why they left out $$v$$ or if $$v$$ is considered to be $$\lambda$$.

However, I tried to proceed like this:

If we decompose $$uaaau^R$$ as $$w=uvxyz$$ as required by the pumping lemma for CFLs, we get $$u=u,\ v=a,\ x=a,\ y=a, z=u^R$$, the first 3 conditions of the lemma are satisfied.

For the last condition, we see that $$uv^ixy^iz=ua^iaa^iu^R\in L$$ for any $$i\geq0$$

Similarly, we can decompose $$uabau^R$$ as $$u=u,\ v=a,\ x=b,\ y=a, z=u^R$$.

So, $$uv^ixy^iz=ua^iba^iu^R\in L$$ for any $$i\geq0$$

Could you please tell me whether my procedure is wrong and how to improve it?

I'm also very confused as to why they didn't mention $$v$$ in their explanation since the pumping lemma requires the string to be divided into 5 sub-strings $$u,v,x,y,z$$.

Please ignore the second example in that material you are studying since it contains some errors. Please see the following corrected version of that example.

Let $$L$$ be the language consisting of all palindromes over $$\{a, b\}$$. The following is an unambiguous grammar for $$L$$. $$S \to aSa\mid bSb\mid a\mid b\mid\lambda$$ What is the minimum pumping length of $$L$$?

The answer is $$1$$.

If a palindrome $$w$$ has even length, the substring $$aa$$ or $$bb$$ is in the middle of the string. That is, $$w = uaau^R$$ or $$w = ubbu^R$$. Suppose $$w = uaau^R$$. We let $$u = u$$, $$v = a$$, $$x = \lambda$$, $$y = \lambda$$, and $$z = au^R$$. The first three conditions are obviously satisfied. For any $$i\ge0$$, $$uv^ixy^i = ua^{i+1}u^R\in L$$. The case that $$w = ubbu^R$$ is similar.

If $$w$$ has odd length, then there are two possibilities:

• $$w = uau^R$$.
We let $$u = u$$, $$v = a$$, $$x=\lambda$$, $$y = \lambda$$, and $$z = u^R$$. The four conditions are satisfied.
• $$w = ubu^R$$.
This case is similar to the case above.

The minimum pumping length cannot be $$0$$ since $$1\le|v|+|y|\le|vxy|\le p$$.

• Thank you so much. Jun 12 at 17:47
• You are welcome. Jun 12 at 17:48