4
$\begingroup$

I believe this statement to be true. And here's my reasoning:

Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ must also be regular.

Do you think my reasoning is valid?

$\endgroup$
  • $\begingroup$ The statement is false, and so your reasoning must be invalid. Consider $L=a^*b$. $\endgroup$ – Yuval Filmus May 7 '18 at 7:19
  • 1
    $\begingroup$ With $L= \Sigma^*$, $L'$ is the most famous example for non-context-free languages. $\endgroup$ – Raphael May 7 '18 at 10:06
  • $\begingroup$ This question appears to be unsuited for this site because questions of the form: "This is the exercise problem, this is my solution. Please grade!" are not interesting for anyone but you. Please see this related meta discussion, and these hints on asking questions about exercise problems. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened. Otherwise, you might want to visit Computer Science Chat and get some feedback there. $\endgroup$ – Raphael May 7 '18 at 10:06
  • 2
    $\begingroup$ @Raphael I think this question is fine. The reasoning here is IMO specific enough to directly address. I don't even see how to ask a more specific question than this. Also, the reasoning is concise enough to be directly answerable, as can be seen in Yuval's answer. $\endgroup$ – Discrete lizard May 7 '18 at 11:10
  • $\begingroup$ It's a yes/no question. Answering 'yes' or 'no' is not very informative. $\endgroup$ – reinierpost May 7 '18 at 20:43
12
$\begingroup$

The statement is false. Consider the language $L = \{a^n b : n \geq 0\}$. Then $L' = \{ a^n b a^n b : n \geq 0 \}$ is not regular (exercise).

The invalid point in your reasoning is a confusion between the following two languages: $L' = \{ ww : w \in L \}$ and $L'' = \{ w_1w_2 : w_1,w_2 \in L \}$. It is $L''$ which is the concatenation of $L$ with itself. Whereas $L'$ need not be regular, $L''$ is always regular when $L$ is.

$\endgroup$
  • $\begingroup$ would you be willing to chat in the cs chat room to discuss? $\endgroup$ – centrinok May 8 '18 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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