0
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$
    – Raphael ♦
    Feb 21, 2014 at 11:50

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ it's not? How come? $\endgroup$
    – user14896
    Feb 21, 2014 at 1:42
  • 1
    $\begingroup$ @user14896 What is the definition of the concatenation of two languages? $\endgroup$
    – David Richerby
    Feb 21, 2014 at 1:43
1
$\begingroup$

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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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