1
$\begingroup$

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:

enter image description here

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$.

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Thank you so much. $\endgroup$ Jun 12, 2023 at 17:47
  • 1
    $\begingroup$ You are welcome. $\endgroup$
    – John L.
    Jun 12, 2023 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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