I am trying to find that $L ={\{w\text{ | } w ∈ {\{a, b\}} * \text{is not a palindrome}\}}$
This is related to this previous question, though in this case I want to explicitly prove it via pumping lemma, since I am unsure my solution is correct. This is what I have:
- $\text{for any } N, \text{ let } w \in L, |w|\ge N$
$w=a^Nb^Na^{N+1}$
- $\text{For any partition } w =xyz , |y|\ge 1, |xy| \le N$
$x=a^r, y=a^s, z=a^{N-r-s}b^Na^{N+1},\text{where }s\ge 1$
- $\exists i \text{ where } xy^iz\notin L$
$i=2\text{ —> }xy^2z=a^{N+s}b^Na^{N+1} \text{ ,where we know that } s\ge 1$
$\text{if }s=1 \text{ then }xy^2z\notin L \text{ and thus L is not regular}$
I am really unsure about the last part. Does the pumping lemma hold if the "pumped word" doesn't belong to L for some specific values of $s$?
Best Answer
There are several problems here. First, you can’t use just any $N$: you need to specify that $N$ is at least as big as the pumping length. Next, the pumping lemma says that there is at least one partition $w=xyz$ such that $|y|\ge 1$, $|xy|\le N$, and $xy^iz\in L$ for each $i\ge 0$; it does not say that this is the case for every partition $w=xyz$ with $|y|\ge 1$ and $|xy|\le N$. And that is why it is indeed illegitimate to pick a specific value of $s$: the pumping lemma just says that there is at least one pair of $r$ and $s$ such that $r+s\le N$, $s\ge 1$, and
$$a^{r+is}a^{N-r-s}b^Na^{N+1}=a^{N+(i-1)s}b^Na^{N+1}\tag{1}$$
is in $L$ for each $i\ge 0$. There is no guarantee that $s=1$. And since $s=1$ is the only value of $s$ for which we can find an $i\ge 0$ making $(1)$ a palindrome, your choice of $w$ simply can’t be made to work.
Because we have no control over $|y|$ beyond the fact that $1\le|y|\le N$, I see no way to use the pumping lemma to show directly that $L$ is not regular. You can use it to show that the language of palindromes over $\{a,b\}^*$, which is the complement of $L$, is not regular and then use the fact that a language is regular if and only if it’s complement is regular to conclude that $L$ cannot be regular. Alternatively, you can use the Myhill-Nerode theorem, as in the answer to this question.