2
$\begingroup$

Given a language $L$ over the alphabet $\{0,1\}$. Let $L^*= \{ w_1w_2...w_n | n \ge 0, w_1,...,w_n \in L\}$.

Prove:

  1. If $L$ is recursive, then $L^*$ is recursive as well.
  2. If $L^*$ is recursive, then $L$ is recursive as well.

For the first proof I have this idea:
If $L$ is recursive, then a turing machine $M_L$ can decide all the words $\{w|w \in L\}$. So $M_L$ can decide $\{w_1,...,w_n | w_1w_2...w_n \in L^*\}$ and appearently it can decide $L^*$ as well.

For the second proof I tried the same but actually it does not work that way. Any hints and ideas?

$\endgroup$
4
$\begingroup$

The second claim is wrong. Let $$ L = \{0,1\} \cup \{010^n : \text{the $n$th Turing machine halts}\}. $$ Then $L^* = \{0,1\}^*$ is recursive, but $L$ isn't recursive.

For the first claim, your proof is not convincing. You need to explain how a Turing machine can decide whether a given word $w \in \{0,1\}^*$ can be written as a sequence of words from $L$. One way is to consider all possible partitions into non-empty subwords, and check whether one of them has the property that all subwords are in $L$.

| cite | improve this answer | |
$\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.