Question

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.

Était-ce utile?

La solution

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.

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top