Proof that the language $ww^R$ is not regular without using the pumping lemma

Question

I am breaking my head over this. Let the alphabet $A$ be given by $A = \{a,b,c\}$ and let

$$L = \{ww^R \mid w \in A^* \}.$$

Prove that the language $L$ is not regular without using the pumping lemma, but using:

• The fact that $\{a^nb^n \in A^* \mid n \geq 0 \}$ is not regular.
• The fact that $\{w \in A^* \mid w \text{ is a palindrome} \}$ is not regular.
• Closure properties of the class of regular languages (such as if $L_1$ and $L_2$ are regular, then $L_1 \cup L_2$ is also regular, etc.).

Answer 1

Suppose that $L$ is regular. Then $L' = L \cap (a+b)^*c^2(a+b)^*$ is also regular. Another description for $L'$ is $$ L' = \{ wccw^R : w \in (a+b)^* \}. $$ Consider now the regular substitution $\sigma$ given by $$ \sigma(a) = \{a\}, \sigma(b) = \{b\}, \sigma(c) = \{a,b,\epsilon\}. $$ Then $L'' = \sigma(L')$ is also regular. But $L''$ is the language of palindromes.

Answer 2

Let

$$ L_1 = \{\ \omega\omega^r \ | \ \omega \in \Sigma^* \} $$ $$ L_2 = \{\ a^nb^n \ | \ n \in \mathbb{N}\ \}$$

Because $\Sigma = \{a, b, c\}$ is finite, $\Sigma^*$ must be countable.

This means we can define a function $f : \Sigma^* \rightarrow \mathbb{N}$ which returns the position of a word $\omega \in \Sigma^*$ in an arbitrary ordering defined by $f$. $f$ is invertible, we define $f^{-1} : \mathbb{N} \rightarrow \Sigma^*$, which returns the word $\omega$ at position $n$ in the enumeration of $\Sigma^*$ as defined by $f$.

Now, since every word $\omega$ is uniquely defined by a natural number $n$, and every word $\omega$ has exactly one unique reverse $\omega^r$, we can define an isomorphism between $L_1$ and $L_2$:

$$ g \colon\ L_1 \rightarrow L_2; \quad \omega\omega^r \mapsto a^{f(\omega)}b^{f(\omega)} $$

$$ g^{-1} \colon \ L_2 \rightarrow L_1; \quad a^nb^n \mapsto f^{-1}(n) f^{-1}(n)^r $$

Since $L_2$ is not regular and we have a bijection between $L_1$ and $L_2$, $L_1$ must not be regular.

This proof works for any finite alphabet $\Sigma$ because the transitive closure of a finite alphabet is always countable.