3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Try the language $L=ab^*a$. $\endgroup$ – Shaull Oct 17 '14 at 21:04
  • $\begingroup$ This would imply that $L_1 = b^*a$, which is regular. It seems that $L_1$, in general, is the set of second-halves of even length palindromes of $L$. $\endgroup$ – David Smith Oct 17 '14 at 21:27
  • $\begingroup$ To get a non-regular language for $L_1$, my intuition is that $L \cap EPAL$ would need to be at least context-sensitive. Why? Because strings in the intersection would need to satisfy two distinct conditions, each requiring memory, simultaneously: they'd need to be even-length palindromes, and the second half would have to have some property that makes $L_1$ non-regular. However, from closure properties, we know that $L \cap EPAL$ is definitely context-free. So my guess would be that $L_1$ is always regular. Anyway, something to think about... there might be a solution farther down that road. $\endgroup$ – Patrick87 Oct 17 '14 at 21:48
  • $\begingroup$ So, then, using your terminology, $L_1 = (1/2(L \cap EPAL))^R$, where $1/2(L)$ consists of the first halves of even-length strings of $L$. $1/2(L)$ I am certain is closed under the class of regular languages. $\endgroup$ – David Smith Oct 17 '14 at 21:55
  • $\begingroup$ Yes, that looks right. In those terms, my observation is that $1/2(L)$ may be regular even if $L$ is not, and my intuition is that any subset $X$ of $EPAL$ for which $1/2(X)$ is non-regular must not be context-free. If I were to try to prove it, I'd make some sort of argument that a PDA couldn't remember enough to accept $w^Rw$ while rejecting those with $w$ that didn't match some other non-regular criterion. Given that our subset of $EPAL$ was formed by intersecting with a regular language, however, means that it must be context-free, implying that $1/2(X)$ is regular. $\endgroup$ – Patrick87 Oct 17 '14 at 22:01
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't understand this answer. What of $M^{\mathrm{op}} \times M$? $\endgroup$ – Gilles Oct 17 '14 at 22:14
  • $\begingroup$ It is the product of monoids $M^{\operatorname{op}}$ and $M$, with multiplication $(a,b)(c,d)=(ac,bd)$. $\endgroup$ – sdcvvc Oct 17 '14 at 22:18
  • $\begingroup$ Unfortunately, I am familiar neither with monoids nor syntactic monoids. Is there a simple way of explaining this? $\endgroup$ – David Smith Oct 17 '14 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.