Problem Detail: If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by $${ww^R|winSigma^*}$$ for some input alphabet $Sigma$, also regular? If not, why not? I’ve been trying to find a proof for this using the pumping lemma, but it seems that selecting any substring towards the middle of the string being pumped could also be of the form ${ww^R|winSigma^*}$, causing the original string to remain in its original form. Here’s a try: $textbf{Theorem:}$ The language, $A$, generated by ${ww^R|winSigma^*}$ is not regular. $textbf{Proof:}$ Assume $A$ is regular (We will use the Pumping Lemma for Regular Languages to show a contradiction). Let the input string $s$ be $ww^R$ and let $p = |w|$. When splitting $s$ into substrings $x, y, z$ such that $s=xyz$ we see that $xy$ must be a substring of $w$ by the third condition of the Pumping Lemma ($|xy|le p$). By the first condition of the Pumping Lemma, we see that all strings of the form $xy^iz$ must be in $A$ for all $i ge 0$. Taking $i$ to be zero, we obtain the string $xw^R$. $|x| < |w^R|$ so $xy^0z notin A$. QED? What if $xw^R$ can still be split so that for some substring $k$, $kk^R = xw^R$? I think I may be overthinking this but it’s really bugging me.
Asked By : mcnnowak
Answered By : AndrewK
You’re over-thinking it on the $xw^R=ww^R$ thing, that’s a red herring. But you’re not over-thinking it by looking for a contradiction, you’re looking in the wrong place. First, your proof that the language is irregular is correct. You’re aiming to show a contradiction. All you need is one counterexample; just one! And you found it already. This may seem paradoxical, but your understanding of how to operate on languages is a little off. As you noted, regular languages are closed under reversal: $L^R = {w^R|win L}$ They are also closed under concatenation: $Lcirc L^R = {wv|win L, vin L^R}$ But, you see, that’s a little different from $L_{mirrored} = {ww^R|win L}$. Look: $L = {$ cat, dog$}$ $L^R = {$ tac, god$}$ $Lcirc L^R = {$ cattac, catgod, dogtac, doggod$}$ $L_{mirrored} = {$ cattac, doggod$}$ There’s your contradiction! You must have thought those last two were the same, when they’re not. Rather, $L_{mirrored} subseteq Lcirc L^R$ And the subset of a regular language is not necessarily regular. edit: I removed a large chunk of this answer, so the comments below will probably be confusing…
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13804
