1
$\begingroup$

Is it true that if $L^*$ is recursive, where $*$ is Kleene star, $L$ is also recursive?

I know that the opposite direction is true:

If $L$ is recursive, then $L^*$ is recursive.

But I don't know how to prove it in this direction.

$\endgroup$
4
  • $\begingroup$ Welcome to the site! In general it helps to repeat your question in the body of the post, and to provide a few links for context. I made some improvements. $\endgroup$ – 6005 Jul 10 '20 at 16:26
  • $\begingroup$ @6005. MathJax is not preferred in title in general unless really helpful. Please read related discussions and many accepted answers. I cannot see how L* and L is inferior to $L^*$ and $L$. $\endgroup$ – John L. Jul 10 '20 at 16:33
  • $\begingroup$ @JohnL. All right, my opinion from being active on mathSE and other sites for a long time is that MathJax is better, but I'm happy to defer to the CS.SE community opinion in this case (from 2018). $\endgroup$ – 6005 Jul 10 '20 at 17:18
  • 1
    $\begingroup$ @6005 Sure, I have edited many posts to use MathJax as well. Typesetting in MathJax for math related formulas and symbols looks so much better in general it is just unfortunate that it was not created and adopted at the start of html. $\endgroup$ – John L. Jul 10 '20 at 17:39
11
$\begingroup$

No.

Take any language $L$ over $\Sigma = \{0, 1\}$ that contains 0 and 1. Then $L^* = \Sigma^*$ (this is recursive, even regular), regardless of what $L$ might be. It could be a not even recursively enumerable language.

$\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.