0

$L=\{ww^Rv\mid v,w\in \{a,b\}^+\}$ Is $L$ regular ?

Edit

Is it ok? Let $p$ will be length of pumping lemma. Then, $a^pb(a^pb)^Rv\in L$. When $a^p(a^pb)^Rv = xyz$
$p\ge |y|\ge 1 $ So $a^{p+k}b(a^pb)^Rv$. Because of the fact that $a^{p+k}b(a^pb)^R$ is not palindrom then $a^{p+k}b(a^pb)^Rv\notin L$. Thanks to pumping lemma we have $L$ is irregular.

Ok ?

user220688
  • 509
  • If $w^R$ is the reverse of $w$, then why do you say that $L_1$ is regular? – Thomas Andrews Mar 31 '15 at 16:01
  • 1
    I have no idea why $ww^{R}$ should be regular. The Language of Palindrome isn't regular because you can't store an arbitrary word to check if it inverse follows. – Manuel G Mar 31 '15 at 16:08
  • look again pleas – user220688 Mar 31 '15 at 17:38
  • Your proof does not work. The word $aa$ is a palindrome and thus $aav \in L$ for each nonempty word $v$. – J.-E. Pin Apr 01 '15 at 17:06
  • I don't understand your comment. Why you talk about $aa$, I got word $a^pb(a^pb)^Rv$ – user220688 Apr 02 '15 at 21:21
  • For $p \geqslant 2$, $a^pb(a^pb)^Rv = aaw$, with $w = a^{p-2}b(a^pb)^Rv$ and thus $a^pb(a^pb)^Rv \in L$. – J.-E. Pin Apr 06 '15 at 20:09
  • It is incredible, but I really don't understand. Look : $p$ is length of pumping lemma. For every word in our language exists partiton such that ( conditions ) And I got word $a^pb(a^pb)^Rv \in L$. ($v$ is anywhere). $a^pb(a^pb)^Rv = xyz$. Because of $|xy|\le p$ , $xy^2z = a^{p+k}b(a^pb)^Rv \notin L$. What's up ?` – user220688 Apr 09 '15 at 19:12

0 Answers0