[Solved]: If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?

Problem Detail: 

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$.

Asked By : David Smith

Answered By : Yuval Filmus

Here is sdcvvc's answer in plain language. Suppose we are given a DFA for $L$ with set of states $S$, starting state $s_0$, accepting states $F$, and transition function $q$. We construct an NFA for $L_1$ as follows. The NFA maintains two states $(s_1,s_2) \in S^2$. Its initial states are $(s,s)$ for all $s \in S$, and its accepting states are $(s_0,f)$ for all $f \in F$. At state $(s_1,s_2)$, upon reading a symbol $a$, the NFA can move to any state $(t_1,t_2)$ such that $q(t_1,a) = s_1$ and $q(s_2,a) = t_2$. This completes the description of the NFA.

This NFA is trying to "prove" that $w^Rw$ is in $L$. The idea is that after reading a prefix $x$ of $y$, say $w = xy$ and so $w^Rw = y^Rx^Rxy$, the NFA will be in state $(q(s_0,y^R),q(s_0,y^Rx^Rx))$. At the beginning, that is when $x = \emptyset$, both states are the same $q(s_0,w^R)$, which the NFA guesses. This explains our initial states. Upon reading a character $a$ while at state $(s_1,s_2)$, the second part of the new state is $t_2 = q(s_2,a)$, while the first part is some $t_1$ satisfying $q(t_1,a) = s_1$. Finally, when we have finished reading the word, that is when $y = \emptyset$, we should be at the state $(s_0,q(s_0,w^Rw)) \in \{s_0\} \times F$, since $w^Rw \in L$. This explains our choice of accepting states.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32033

3.2K people like this

 Download Related Notes/Documents