I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free.
In case there are none how do you prove it?
$\begingroup$
$\endgroup$
-
1$\begingroup$ Can be answered with the same techniques as cs.stackexchange.com/questions/1549 $\endgroup$ – sdcvvc May 25 '12 at 20:54
-
2$\begingroup$ Hint: all languages which contain the alphabet have a very simple Kleene closure. $\endgroup$ – Raphael♦ Dec 15 '14 at 22:58
$\begingroup$
$\endgroup$
$L = \{a^n b^n \mid n\in\mathbb{N}\}$ is context-free but not regular (classical example). So is $L' = \{a^n b^n \mid n\in\mathbb{N}\} \cup \{a,b\}$.
$L'^\ast = \{a,b\}^\ast$ is regular.
answered May 25 '12 at 20:59
Gilles 'SO- stop being evil'Gilles 'SO- stop being evil'
38.3k7 gold badges102 silver badges166 bronze badges
-
2
-
