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$ Jul 10, 2020 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, 2020 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$ Jul 10, 2020 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, 2020 at 17:39

1 Answer 1

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

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