Problem Detail: Consider the following language: $$ L_1={uu^rv mid u,vin{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?
Asked By : farseer
Answered By : sdcvvc
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 $(010101cdot 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7271 Ask a Question Download Related Notes/Documents
