patternMinor
Is this language regular?
Viewed 0 times
thisregularlanguage
Problem
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?
$$ 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?
Solution
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.
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.
Context
StackExchange Computer Science Q#7271, answer score: 5
Revisions (0)
No revisions yet.