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!

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 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 Jun 2 at 11:10

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.