0
$\begingroup$

If $L\notin$ RE, can there be a language $L'\subseteq L$ such that $L'\in$ RE? Or is it necessarily true that $L'\notin$ RE for all $L'\subseteq L$.

$\endgroup$
2
  • 3
    $\begingroup$ Consider the empty language. $\endgroup$ Nov 8 '21 at 6:13
  • 3
    $\begingroup$ More generally: whenever faced with a question of the form "is there any language such that" or "are all languages such that", always try the empty language and the universal language (of all strings) first. $\endgroup$ Nov 8 '21 at 11:00
2
$\begingroup$

Take any language $L\notin RE$. Now, $\emptyset \subseteq L$, and clearly $\emptyset\in RE$.


FYI, the converse is also not necessarily true: $L\subseteq \Sigma^*$, and $\Sigma^*\in RE$.

$\endgroup$
0
0
$\begingroup$

Yes; as others have said, the empty language $\varnothing$ is recognizable, and it's a subset of every language.

For a less trivial example, let $L$ be an unrecognizable language. Pick any finite subset of strings $D$ from $L$. That subset $D$ is a recognizable language—in fact, it's a regular language! The algorithm that recognizes it is a lookup table that checks whether the input matches any one of the hard-coded strings from $D$.

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