Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 4 down vote accepted

Nice question. It is not regular.

Notice that this language consists of words where some nonempty prefix is an even palindrome.

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.

share|cite|improve this answer
Agree with everything you said. I proved that this language is not regular by proving that Rank(L)=infinity. No i wonder if Pumping lemma works here or not:) – farseer Dec 9 '12 at 19:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.