Let $L$ be a regular language.

Is the language $L_2 = \{ ww | w \in L \}$ context-free? Does it have a name?

  • $\begingroup$ Not regular, not even when $L=\{a,b\}^*$. See for example cs.stackexchange.com/q/11759, cs.stackexchange.com/q/38459/4287 or cs.stackexchange.com/q/45681/4287 . $\endgroup$ Oct 27 at 11:53
  • $\begingroup$ @HendrikJan thanks, see my edit, I'm also interested in the name of the language $\endgroup$ Oct 27 at 11:55
  • $\begingroup$ OK, I should have added the language for $L=\{a,b\}^*$ is not context-free. Usually one of the standard examples for which the pumping lemma for context-free languages is applied. I do not know of a well-established name. The last question I linked to uses "repeat(L)". $\endgroup$ Oct 27 at 13:06


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.