Multiple-Choice Questions about decidability

Question

I'm working on old MC-Questions about decidability und don't have the answers to the following ones:

1.) $L_1$ and $L_2$ are not decidable $\Rightarrow$ No superset of $L_1 \cup L_2$ is decidable

2.) For Turing-acceptable languages L is "L = $\emptyset$" a non-trivial property.

3.) There are context-free languages $L_1$ and $L_2$ so that $L_1 \cap L_2$ is not decidable.

4.) $L$ is decidable $\Leftrightarrow$ $L \le \{0\}^* \cdot \{1\}^*$

I think 1.) is false, because $\Sigma^*$ as a superset of many undecidable languages for example is decidable and 2.) is true, because there are Turing-acceptable languages with (exactly one) and without the property. I have no idea at 3.) and 4.).

Answer 1

Regarding 1 - $\Sigma^*$ is a superset of every language, not just "many". This is a very general and important point: the measure of how "complicated" a language is, is not in a direct correlation with how "big" the language is.

In 2 - you are correct.

For 3 - the answer is no - if $L_1$ and $L_2$ are CFL, then $L_1\cap L_2$ is decidable. Indeed - decidable languages are closed under intersection, and every CFL is decidable.

As for 4 (assuming that by $\le$ you mean "mapping-reducible") - observe that $0^*1^*$ is a regular language, and in particular - decidable. Thus, if $L\le_m 0^*1^*$, then surely $L$ is decidable.

Conversely, assume that $L$ is decidable, then there exists a mapping reduction from $L$ to every non-trivial language. Indeed, you can decide $L$ within the reduction, and just output a fixed string. So the answer is yes.