Is there a context free, non-regular language $L$, for which $L^*$ is regular?

Question

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?

Can be answered with the same techniques as cs.stackexchange.com/questions/1549 — sdcvvc, May 25 '12 at 20:54
Hint: all languages which contain the alphabet have a very simple Kleene closure. — Raphael, Dec 15 '14 at 22:58

Gilles 'SO- stop being evil' · Accepted Answer · 2012-05-25 20:59:22Z

20

$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

40.9k7 gold badges108 silver badges172 bronze badges

2

$\begingroup$ Brute-force, but valid. $\endgroup$
– Raphael ♦
May 25 '12 at 22:51
$\begingroup$ $L' = L$, actually... $\endgroup$
– vonbrand
Nov 30 '16 at 1:48
$\begingroup$ @vonbrand ... actually not. $\endgroup$
– Rick Decker
Oct 8 '20 at 19:00

Add a comment |

1 Answer 1