Question

Explain the following statements and determine whether they are true or false.

1) Complement of a CFL need not be recursive
2) If L is recursive then (L)^+ is also recursive.
3) If L1 is recursive and L2 is recursively enumerable then L2 - L1 is need not be recursively enumerable.
4)Recursive sets are closed under complement and substitution.

Answer 1

Answer on Question#38225 – Math - Other

1) Complement of a CFL need not be recursive. False. All context-free languages are recursive.

2) If $L$ is recursive then $L^*$ is also recursive. True. Recursive languages are closed under the following operations. That is, if $L$ is recursive language, then $L^*$ is recursive as well.

3) If $L_1$ is recursive and $L_2$ is recursively enumerable then $L_2 - L_1$ is needed not be recursively enumerable. True. Recursively enumerable languages are not closed under set difference or complementation. The set difference $L_2 - L_1$ may or may not be recursively enumerable. If $L_1$ is recursively enumerable, then the complement of $L_1$ is recursively enumerable if and only if $L_1$ is also recursive.

4) Recursive sets are closed under complement and substitution. True. Recursive languages are closed under the following operations: the intersection $L_1 \cap L_2$, the complement of $L$, the image $\varphi(L)$ under an e-free homomorphism $\varphi$ (substitution).