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

Improve this question
$\endgroup$
5
  • $\begingroup$ The statement is false, and so your reasoning must be invalid. Consider $L=a^*b$. $\endgroup$
    – Yuval Filmus
    Commented May 7, 2018 at 7:19
  • 1
    $\begingroup$ With $L= \Sigma^*$, $L'$ is the most famous example for non-context-free languages. $\endgroup$
    – Raphael
    Commented May 7, 2018 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
    Commented May 7, 2018 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 ♦
    Commented May 7, 2018 at 11:10
  • $\begingroup$ It's a yes/no question. Answering 'yes' or 'no' is not very informative. $\endgroup$
    – reinierpost
    Commented May 7, 2018 at 20:43

1 Answer 1

Reset to default
14
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ would you be willing to chat in the cs chat room to discuss? $\endgroup$
    – centrinok
    Commented May 8, 2018 at 23:53

Your Answer

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

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