# A flawed theorem about regular languages

I am struggling with this question for a very long time and just can't find the flaw. So I am given a false Theorem:

The language $$\{awwa \mid w \in \{a,b\}^* \}$$ is regular.

Well, that part is obvious, we can prove that the language is not regular using the pumping lemma.

The question I am asked is to find the flaw in the "proof" for this theorem:

Let

$$\qquad L_1 = \{ aw \mid w \in \{a,b\}^* \}$$

$$\qquad L_1^R = \{ wa \mid w \in \{a,b\}^* \}$$

Let $$L_2 = L_1 L_1^R = \{ awwa \mid w \in \{a,b\}^*\}$$ be even-length palindromes that begin and end with an $$a$$. Since $$L_1$$ is regular, and the class of regular languages is closed under reversal and concatenation, we conclude $$L_2$$ is also regular.

Can you find the flaw? I could build a DFA for $$L_1$$ and $$L_1^R$$, so I know they are regular. And regular languages are closed under reversal and concatenation.

But, however, $$L_2$$ is still not regular, so where is the mistake in the "proof"?

• Try writing down some words from $L_1 \cdot L_1^R$ -- you'll notice quickly what's wrong. (Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction.) Feb 21, 2014 at 11:50

The concatenation of $L_1$ and $L_1^{\mathrm{R}}$ is not $\{awwa\mid w\in\{a,b\}^*\}$.
Remember that for some languages $L_1$, $L_2$, $LL = \{uv \;\colon\; u \in L_1,\;v \in L_2\}$. Back to your question, is it the case that for every $au \in L_1$ and $va \in L_1^R$ that $auva$ is an even length palindrome that begins and ends with $a$?