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.

有帮助吗?

解决方案

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.

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top