# Prove that $L= \{w|$ $w$ ends with a palindrome of length greater than or equal to $4\}$ is nonregular using the pumping lemma.

The alphabet is $\{a, b\}$

Hi, I tried this:

Assume to the contrary that $L$ is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s$ be the string $a^{p}ba^{p}$. Because $s$ is a member of $L$ and $s$ has length more than $p$, the pumping lemma guarantees that $s$ can be split into three pieces, $s=xyz$, satisfying the three conditions of the lemma:

1. for each $i\ge0,xy^{i}z\in L,$

2. $|y|>0, and$

3. $|xy| \le p.$

$x=a^{s}, y=a^{t},z=a^{p-s-t}ba^{p}$

for $i=0,$ $xy^{0}z \in L$

I don't understand how to solve it.

Thanks.

## 1 Answer

Z = uvw.

We’ll define x = 0^(p+1)1^(p+1)0^(p)1^(p).....000111001101.

we’ll define Z = x^R • x (Reverse of x concatenated with x).

Z is clearly in L (notice how I defined x so that Z is definantly bigger than 4).

Now, no matter what v is (obviously within the constraints of the pumping lemma), if we take i = 0 the word produced will not be in L (this is easily proven using the zero’s at the beginning of x).

• I don’t understand why this post was deleted, I thought concise and correct answers are optimal. – Euclid Aug 19 '18 at 8:49
• @Leucippus (forgot to tag) – Euclid Aug 19 '18 at 13:32