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?
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 $(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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7271
0 comments:
Post a Comment
Let us know your responses and feedback