patternMinor
Is the language that accepts strings concatenated with their reverse regular?
Viewed 0 times
theacceptsconcatenatedreversewithregularlanguagethatstringstheir
Problem
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.
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.
Solution
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 = \{$
$L^R = \{$
$L\circ L^R = \{$
$L_{mirrored} = \{$
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...
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...
Context
StackExchange Computer Science Q#13804, answer score: 4
Revisions (0)
No revisions yet.