1
$\begingroup$

Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$.

From my understanding of the Pumping Lemma, to show it would hold, I need to decompose $ s $ into $ s = xyz $ such that (1) $ xy^{i}z \in A, i \geq 0 $, (2) $ y \neq \epsilon $, and (3) $ |xy| \leq p $.

For cases where $ p \geq 2 $, the decomposition makes sense to me and appears to be quite trivial. For example, when $ p = 2 $, then $ s = aaaa $, and can be decomposed into $xyz$ where $x = a, y = a, z = aa $, which satisfies the conditions above above. Induction could be used to show this holds for larger values of $ p $.

However, I am struggling on the case where $ p = 1 $. Here, $ s = aa $, and it seems like there are not enough symbols to decompose into $ xyz $. My best guess would be to choose $ x = a, y = a, z = \epsilon $, but for some reason this doesn't feel legal -- can you ad-hoc assign pieces of $ xyz $ to be $ \epsilon $? Also, I believe this decomposition would fail to satisfy condition (3) above. Can you offer some guidance on understanding what is happening in the case where $ p = 1 $?

Thanks for your time!

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to COMPUTER SCIENCE @SE. There are pumping lemmata for different Chomsky types of languages; you quoted the one for regular languages. Note that $y$ is the only part required to be non-empty. $\endgroup$
    – greybeard
    Oct 6 '20 at 7:55
0
$\begingroup$

The empty string is a legitimate string, just like the empty set is a legitimate set. We say that a word $w \in \Sigma^*$ can be pumped with respect to parameter $p \geq 1$ and a language $L$ if there exists a decomposition $w = xyz$, where $x,y,z \in \Sigma^*$ satisfy the following three requirements:

  • $|xy| \leq p$.
  • $y \neq \epsilon$.
  • $xy^iz \in L$ for all $i \geq 0$.

A mathematical definition hides nothing. A word can be pumped if it satisfies the definition as stated. No more, no less.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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