0
$\begingroup$

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.).

$\endgroup$
1
$\begingroup$

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.

$\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.