5
$\begingroup$

I have been looking around and i cant seem to find an example of such case that a non-regular $L$ has a non regular $L^*$. Is it possible? If so, can you provide an example of such case please?

$\endgroup$
5
  • 1
    $\begingroup$ Do you know any non regular language $L$? Have you tried with one of them? $\endgroup$ – Nathaniel May 18 at 22:08
  • $\begingroup$ I do, for example, L = {a^nb^n | n e N}. I have tried but am still having troubles with this topic. $\endgroup$ – Justin Park May 18 at 22:20
  • 1
    $\begingroup$ I am sure that you can succeed in proving that for this language, $L^*$ is not regular, since the same usual proof (with pumping lemma) works. $\endgroup$ – Nathaniel May 18 at 22:21
  • $\begingroup$ Thank you guys so much! $\endgroup$ – Justin Park May 18 at 22:23
  • $\begingroup$ For your information: if $L$ is a language over a single letter alphabet, then $L^*$ is always regular, whetever the complexity of $L$. But that is a special case of course. $\endgroup$ – Hendrik Jan May 20 at 1:39
4
$\begingroup$

Take the Dyck language $D$. It is context-free but not regular and satisfies $D^* = D$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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