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?

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

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.

| cite | improve this answer | |
  • $\begingroup$ 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:) $\endgroup$ – farseer Dec 9 '12 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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