4
$\begingroup$

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|w\in\Sigma^*\}$$ 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|w\in\Sigma^*\}$, causing the original string to remain in its original form.

Here's a try:

$\textbf{Theorem:}$ The language, $A$, generated by $\{ww^R|w\in\Sigma^*\}$ 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.

$\endgroup$
  • $\begingroup$ Also, I know this language is context-free but regular languages are a subset of the context-free languages and I'm looking to prove that this language is context-free but not regular. $\endgroup$ – mcnnowak Aug 18 '13 at 21:42
  • $\begingroup$ But the regular languages are not closed under reversing, as indeed $A$ shows, as proven in your theorem! $\{ww^R \mid w \in \Sigma^*\}$ is regular if and only if $|\Sigma|=1$. $\endgroup$ – Pål GD Aug 18 '13 at 23:06
  • 1
    $\begingroup$ Do you confuse this with the following? Let $A$ be a regular language. Then $A^R$ is also regular, where $A^R = \{w^R \mid w \in A\}$? That is, reverse every string in $A$ and you have a regular language as well. $\endgroup$ – Pål GD Aug 18 '13 at 23:09
  • 1
    $\begingroup$ Let me stress that your proof is wrong as stated. You need to come up with a word $w$ so that $xw^R$ cannot be written as $kk^R$. As mentioned by Pål, this will be impossible if $|\Sigma|=1$. $\endgroup$ – Yuval Filmus Aug 19 '13 at 1:16
3
$\begingroup$

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|w\in L\}$

They are also closed under concatenation:

$L\circ L^R = \{wv|w\in L, v\in L^R\}$

But, you see, that's a little different from $L_{mirrored} = \{ww^R|w\in L\}$. Look:

$L = \{$ cat, dog$\}$

$L^R = \{$ tac, god$\}$

$L\circ 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 L\circ 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...

$\endgroup$
  • $\begingroup$ A is correct, B is wrong. Suppose for example that $w = abaa$ and $x = ab$; we get $xw^R = abaaba = zz^R$ for $z=aba$. $\endgroup$ – Yuval Filmus Aug 19 '13 at 0:18
  • $\begingroup$ That is actually what I mean. You can't use $xw^R$ in the pumping lemma unless you know it it's in the language. Since $xw^R$ is generated through the pumping lemma, it can only be in the language if the language is regular. Therefore, you can't use $xw^R$ to prove that the language is regular. (It would be circular reasoning.) The entire thing with $xw^R$ is a red herring. In fact, it looks to me like he proves the language is irregular before ever reaching that point. I'll see about clarifying my answer. $\endgroup$ – AndrewK Aug 19 '13 at 0:28
  • $\begingroup$ Andrew, you're getting your logic wrong. You're assuming that the language is regular, and then you find a contradiction with the switching lemma. The switching lemma states that if some word $v$ is in the language, then a bunch of other words $V$ are in the language. In order to obtain a contradiction, you arrange that $v$ is in the language, but one of the words in $V$ isn't. In our case, $v = ww^R$, and you need to arrange that $xw^R \in V$ isn't in the language. $\endgroup$ – Yuval Filmus Aug 19 '13 at 0:31
  • $\begingroup$ Woah, slow down buddy! I think you're misreading. I'm saying his pumping lemma alone is enough to show contradiction: the language is not regular. Switching lemma? I don't even get into that. He thinks there's a problem, and can't find it. But his trouble is in understanding what happens when you concatenate languages. I'll say it plainly: The $xw^R=xw^R$ business is a red herring. No help at all. We can ignore it completely and have an answer. $\endgroup$ – AndrewK Aug 19 '13 at 0:43
  • 2
    $\begingroup$ @Raphael, unfortunately the comments are not obsolete. This answer (first part) is wrong. $\endgroup$ – Yuval Filmus Aug 22 '13 at 19:49
3
$\begingroup$

Here is a short solution. Let $L = \{ uu^r \mid u \in A^*\}$. If $A$ is empty or contains only one letter, then $L$ is regular. Suppose now that $A$ contains at least two letters, say $a$ and $b$. Using the pumping lemma, it is easy to see that the language $L \cap a^*bba^* = \{a^nbba^n \mid n \geqslant 0 \}$ is not regular. Therefore $L$ is not regular, since the intersection of two regular languages is regular.

$\endgroup$
  • $\begingroup$ You don't need to intersect it with $a^*bba^*$. Just take $n$ larger than the pumping length. $\endgroup$ – Yuval Filmus Aug 19 '13 at 16:32
  • $\begingroup$ @yuval-filmus I don't get your argument. If you just apply the pumping lemma to $a^nbba^n$, you may have $bb$ as a pumping factor, but $a^n(bb)^*a^n \subset L$. I probably missed something. $\endgroup$ – J.-E. Pin Aug 19 '13 at 18:15
  • 1
    $\begingroup$ The pumping lemma assures you that the pumped part is within the first $p$ symbols, where $p$ is the size of the minimal DFA for the language. Other versions allow even more control, but that's enough here. If $n \geq p$ then the pumped part is inside the first $a^n$, so you can guarantee to avoid the problematic $a^n(bb)^*a^n$. $\endgroup$ – Yuval Filmus Aug 19 '13 at 18:26
  • $\begingroup$ @yuval-filmus Ooops. You're right of course. $\endgroup$ – J.-E. Pin Aug 19 '13 at 19:39
2
$\begingroup$

Hint: Find a word $w$ so that for every proper substring $x$ of $w$, $xw^R$ is not of the form $zz^R$. As mentioned by Pål, you will only be able to find $w$ if the alphabet contains at least two letters. Also, naturally $w$ must depend on the pumping length $p$ (since your argument relies on $|w| \geq p$).

Not every word $w$ works, so your proof isn't complete. You have identified this problem yourself. Every step in a proof needs to be justifiable, otherwise it's not a proof. If there is a step you're not sure about, then it's not a proof.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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