# 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.) – Raphael Feb 21 '14 at 11:50

The concatenation of $L_1$ and $L_1^{\mathrm{R}}$ is not $\{awwa\mid w\in\{a,b\}^*\}$.

• it's not? How come? – user14896 Feb 21 '14 at 1:42
• @user14896 What is the definition of the concatenation of two languages? – David Richerby Feb 21 '14 at 1:43

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$?