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$
5
  • $\begingroup$ Try the language $L=ab^*a$. $\endgroup$
    – Shaull
    Commented Oct 17, 2014 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$ Commented Oct 17, 2014 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
    Commented Oct 17, 2014 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$ Commented Oct 17, 2014 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
    Commented Oct 17, 2014 at 22:01

2 Answers 2

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$
3
  • $\begingroup$ I don't understand this answer. What of $M^{\mathrm{op}} \times M$? $\endgroup$ Commented Oct 17, 2014 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
    Commented Oct 17, 2014 at 22:18
  • $\begingroup$ Unfortunately, I am familiar neither with monoids nor syntactic monoids. Is there a simple way of explaining this? $\endgroup$ Commented Oct 17, 2014 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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