# Is this language regular?

Consider the following language: $$L_1=\{uu^rv \mid u,v\in\{0,1\}^+\}.$$ that means that neither $u$ nor $v$ can be $\varepsilon$. As usual $u^r$ refers to $u$ reflected.

I think that this language is not regular, but i am not sure. Any ideas?

• Hint: $v$ can be any string. – Dave Clarke Dec 9 '12 at 17:02
• Yeah. I done it suing Equivalence Classes. I tried using pumping lemma and failed. Perhaps pumping lemma working in this language. – farseer Dec 9 '12 at 17:15
• Actually, $v$ cannot be any string. I missed the fact that $u,v\in\{0,1\}^+$. My mistake. – Dave Clarke Dec 9 '12 at 18:15

Intersect $L$ with $(01)^{+} (10)^{+}$. If a word of this form has a palindromic prefix: $(01)^n (10)^m = u u^R v$ and $u \neq \varepsilon$, then the center of palindrome must be between the group of $01$ and the group of $10$. For example, take the word $0101011010101010$. The only possibility of breaking a prefix into a palindrome is $(010101\cdot 101010)\cdot1010$. (I leave the proof of this statement to you.)
Therefore, $L \cap (01)^{+} (10)^{+}=\{(01)^n (10)^m : m > n \geq 1\}$. However, this language is not regular - for example, each prefix $(01)^n$ is in a different Myhill-Nerode class.