patternModerate
Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular
Viewed 0 times
provingregularthatthen
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#91584, answer score: 13
Revisions (0)
No revisions yet.