Prove that the set of palindromes are not regular languages using the pumping lemma.

Question

Firstly I pick a language $xyz$ where $x = \epsilon$, $y = (abb)^{k}$, $z = (bba)^{k}$ where $|y| \ge$ the number of states in the automaton representing my language. Then $xyz = (abb)^k(bba)^k$ is a palindrome.

Now I split $y$ into $uvw$, where $v \ne \epsilon$ contains a state visited more than once. If the language is regular then $xuv^iwz$ is within the language $\forall i \ge 0$.

I choose $i = 2$, then $uv^2w = (abb)^n$ where $n > k$.

Then $xuv^2wz = (abb)^n(bba)^k$ where $n > k$, which is not a palindrome.

Firstly, is my reasoning for this particular proof correct? I'm unsure about how to properly apply the pumping lemma to this problem. And secondly the question asks me to state a proof for palindromes in general, whereas I only attempted to prove it for a single case. Is there an example I can choose which proves the conjecture for all palindromes? I assume not, seeing as I can't think of how that could be represented using regular expressions.

Answer 1

Consider the language $$ L = \left\{ w^p : w \in L \right\}, L \subseteq A^{*}.$$ Where $A$ is the input alphabet of the automaton that recognizes $L$.

where $w = a_1a_2...a_n, \left| w \right| = n $ and $w_p = a_na_{n-1}...a_1, \left| w_p \right| = n $

From a general approach using Kleene's theorem we know that a language is regular iff it is rational. However, in order for language $L$ to be regular/recognisable from a finite automaton it must have an infinite set of states, which is impossible. Thus, Kleene's theorem guarantees that this language is NOT regular.

Things are getting a bit harder when we have to prove our claim using the pumping lemma.

By presuming the language is regular, there exists a number $p$ (length of pump) so that the following conditions are true:

$$ \forall i \geq 0, xy^iz \in L$$ $$ \left| y \right| > 0 $$ $$\left| xy \right| \leq p $$

You should try with the word $w_p$ and go through all 3 conditions of the pumping lemma. The key to the solution is condition Number 3 since the first condition cannot always lead to a contradiction.

Answer 2

Your proof is no good; the basic idea is fatally flawed. You are asked to use the pumping lemma to prove that $P$, the set of all palindromes, is irregular. Instead, you picked some subset of $P$, namely the set of strings $$X =\{\epsilon, \mathtt{abbbba}, \mathtt{abbabbbbabba}, \ldots\},$$ and tried to show that other set is irregular. But even if you were to succeed in that, it wouldn't help you solve the problem, because the question wasn't about $\epsilon, \mathtt{abbbba}, \mathtt{abbabbbbabba}, \ldots$; it was about the set of all palindromes.

Showing that $X$ is not regular does not help you show that the set of palindromes was irregular; why should it? Well, I guess you want to say “The set of palindromes contains $X$, and $X$ is not regular, so the larger set can't be regular either.” But this is nonsense. The language $(\mathtt{a}+\mathtt{b})^\star$ contains $X$ also, and it is as regular as can be.

---

The way you do a proof using the pumping lemma should look like this. You imagine playing a game against an adversary, Mr. Pumping Lemma.

1. Mr. Pumping Lemma gives you a constant $p\gt 0$, and claims that all palindromes of length $p$ or greater have a pumpable part near the beginning.
2. You pick some single palindrome $x$ whose length is at least $p$. You say “This string $x$ has length $p$ or greater, and does not have a pumpable part near the beginning.”
3. Mr. Pumping Lemma says “yes, it does” and divides your string $x$ into $uvw$ so that $|uv|\le p$, $|v|\gt 0$. The $v$ part is the pumpable part, and $|uv|\le p$ means that it is close to the beginning of the string.
4. You pick some number $n \ne 1$ and show that $uv^nw$ is not a palindrome. (What $n$ should you pick here?) If you can do this, you say “see, I pumped $v$ as you said, and the result was not a palindrome,” and you win. If not, Mr. Pumping Lemma wins.

You must make a clever move in step 2 so that no matter what Mr. Pumping Lemma does is step 3, you can always win in step 4. If you pick the wrong string in step 2, Mr. Pumping Lemma can confound you. For example, if you were to pick $x = \mathtt{a}^p$ in step 2, that would be a bad move, because then in step 3, Mr. Pumping Lemma could take $u=\mathtt{a}^i, v = \mathtt{a}^{p-i}, w = \epsilon$, and then no matter what $n$ you picked in step 4, the resulting $uv^nw$ would still be a palindrome and you would lose.

Fortunately in this case it's not hard to make a good choice in step 2. I suggest that you try $x=\mathtt{a}^{p+1}\mathtt{b}\mathtt{a}^{p+1}$ and see how that goes.

Answer 3

Your proof is incorrect, for instance you only handle a subset of palindromes (and regular languages can have non-regular subsets). I'm not quite sure what you're trying to do there, but for reference here's my version of the proof using the pumping lemma. I hope it opens up valuable insights.

In the proof, I will assume the alphabet to consist of at least two distinct symbols (as palindromes are a regular language if there is only one symbol in the alphabet).

My version of the proof

(using $s^R$ to denote the reverse of $s$)

Let $L = \{s : s = s^R\}$ or the set of all palindromes (strings that are equal to their reverse strings).

If $L$ is regular, there must be a pumping length $p \ge 1$ so that for each $s \in L$, if $|s| \ge p$ we can write $s$ as $xyz$ so these three conditions apply:

• $y \neq \epsilon$ ($y$ has at least one character/symbol, in other words $|y| \ge 1$)
• $|xy| \le p$
• for all $i \in \mathbb{N} \cup \{0\}$, $xy^iz \in L$

Let $s = a^pba^p$. We can see $s$ is a palindrome, so $s \in L$. Also, $|s| = 2p + 1 \ge p$.

Because of the two first conditions, all possible $xyz$ divisions of $s$ are in the following form:

• $x = a^k$
• $y = a^m$
• $z = a^{p-m-k}ba^p$

for some non-negative integers $k, m$ so that $k + m \le p$ and $m \ge 1$.

Now let's demonstrate that $xy^iz \in L$ doesn't hold for some values of $i$.

For example, let $i = 2$. Then $$xy^2z = xyyz = a^ka^ma^ma^{p-m-k}ba^p$$

which can be simplified further as $$a^ma^pba^p = a^{p+m}ba^p$$

The reverse string, $(xy^2z)^R$ is $a^pba^{p+m}$. Because we know that $m \ge 1$, it follows that $$a^pba^{p+m} \neq a^{p+m}ba^p$$ Therefore, $xy^2z \notin L$ under any possible divisions $xyz$ while following the three conditions ruled by the lemma. Hence, $L$ must be non-regular.

Two important notes

• You can choose any string $s \in L$, as long as $|s| \ge p$. Make life easy for yourself and pick a string that makes the rest of the lemma easy to apply. I picked $a^pba^p$ simply to reduce the complexity of different $xyz$ divisions.
• For a language to be non-regular, you must prove there are no possible divisions $xyz$ that are possible according to the three criteria. It's not enough to demonstrate that some $xyz$ division fails at the $xy^iz \in L$ phase.