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, 2021 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$ May 18, 2021 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, 2021 at 22:21
  • $\begingroup$ Thank you guys so much! $\endgroup$ May 18, 2021 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$ May 20, 2021 at 1:39

1 Answer 1

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 and acknowledge you have read our privacy policy.

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