2

Let $$L = \{ ww^rx \mid w,x \in \{a,b \}^+\} $$

where $\{a,b\}^+$ means the set of words over $\{a,b \}$ that has at least length 1, and $w^r$ is the reverse of $w$.

I'm trying to prove that this language satisfies the pumping lemma, but is not a regular language.

Let me show my attempt. Let $N=1$ and $p \in L$. It's obvious that $|p|>1$ by definition of $L$. Afterwards, consider $x= \varepsilon$, $y = $ first letter of $p$ (wlog, let consider $y=a$) and $z = $ rest of the word. It's clear that $|xy|\leq 1$ and $|y|>0$. Now, we got to prove that $$ \forall i\geq 0: \ \ p_i = xy^iz = a^iz \in L $$

For $i=1$ we're done, since by assumption $p \in L$. For $i\geq 2$, we have that $p_i = a^iz = (aa)a^{i-2}z$. Therefore, we could consider $w=a$ and $p_i = (aa)a^{i-2}z = ww^ra^{i-2}z \in L$

Here is where I got in troubles. Let consider the case $i=0$, since $p \in L$ there exist $w,x \in \{a,b\}^+$ such that $p = ww^rx$. As we assume, wlog, that $y=a$, follows that $w = a\tilde{w}$ with $\tilde{w} \in \{a,b \}^*$. If $|\tilde{w}|>0$ it's clear that $p_0 = \tilde{w}\tilde{w}^raz \in L$. My problem is what can I do if $|\tilde{w}| = 0$?

On the other hand, I want to prove that this language is not regular. I was proceding by contradiction, trying to use closure properties and the fact that $\tilde{L} = \{ ww^r \mid w \in \{a,b \}^+ \}$ is not regular. But I haven't found the contradiction, yet.

Regards.

Sorombo
  • 663

1 Answers1

2

You're going to need a pumping length of at least $4$, since otherwise you have to break up the string $aaa$, and no shorter strings lie in $L$. If you choose a pumping length of 4, then you can use your method except in the case where the string starts $aab$ or $bba$, in which case you choose $x$ to be the first two letters and $y$ to be the third letter.

The Myhill-Nerode theorem seems to be a reasonable tool for proving that $L$ is not regular. The strings $x= (ab)^i$ and $y= (ab)^j$ for $i<j$ appear to be distinguished by the string $z = (ba)^ia$ in the sense that $xz \in L$ and $yz\not\in L$. Maybe there are proofs that don't use such a result, I'm not sure.

Rolf Hoyer
  • 12,399