# Applying the Pumping Lemma to aspecific string

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

• 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. Oct 6, 2020 at 7:55
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$$.