patternMinor
If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?
Viewed 0 times
thel_1maymustnonregularlanguage
Problem
The reverse, $w^{R}$, of a string $w = w_1w_2...w_n$ is the string $w_n...w_2w_1$. Suppose that L is a regular language. Must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular? Explain.
Intuitively, I suspect that $L_1$ may be nonregular, since the set of even-length palindromes of an arbitrary regular language $L$ isn't necessarily regular. However, I'm not sure that the pumping lemma can be used to prove the non-regularity of $L_1$.
Intuitively, I suspect that $L_1$ may be nonregular, since the set of even-length palindromes of an arbitrary regular language $L$ isn't necessarily regular. However, I'm not sure that the pumping lemma can be used to prove the non-regularity of $L_1$.
Solution
It will be regular.
Let $M$ be the syntactic monoid of $L$ and consider the monoid $M^{\operatorname{op}} \times M$ (where $M^{\operatorname{op}}$ is $M$ with multiplication flipped).
Let $M$ be the syntactic monoid of $L$ and consider the monoid $M^{\operatorname{op}} \times M$ (where $M^{\operatorname{op}}$ is $M$ with multiplication flipped).
Context
StackExchange Computer Science Q#32033, answer score: 2
Revisions (0)
No revisions yet.