2
$\begingroup$

I have this assignement that asks to say if the following statement is true or false, and possibly justifying the answer:

"Let L₁, L₂ be decidable languages.
For every language L s.t. L₁ ⊆ L ⊆ L₂, L is decidable too

My first idea was to use the Halting Problem Language as L and show that is not decidable to prove the statement is false.

I tried to ask the Professor and he confirmed me that the assignment is false but he gave me a hint about explicitly describing the two languages L₁ and L₂, but I don't know which one would fit for this scope.

Thank you!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Your statement is false. Indeed, if $L$ is any language over $\Sigma$, then $$ \emptyset \subseteq L \subseteq \Sigma^*.$$

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Or to generalize: when asked a question about languages in general, first ask yourself what happens for the trivial languages, the empty set and the universal set ($\Sigma^*$). $\endgroup$
    – reinierpost
    Commented Jun 2, 2020 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.