0
$\begingroup$

I should prove or give a counterexample to the above statement.

In my opinion, this statement is false but I don't manage to find the right counterexample.

My idea was to define $C = Σ^*$ because $Σ^*$ is decidable and contains all the undecidable languages but I fail to find an undecidable language that contains a decidable language.

Improve this question
$\endgroup$
3
  • $\begingroup$ A simple hint: have you considered finite languages? And, maybe, the smallest of them? $\endgroup$
    – Tonita
    Apr 23 at 9:49
  • $\begingroup$ @Tonita for B? aren't all finite languages decidable? $\endgroup$
    – RedYoel
    Apr 23 at 9:53
  • 1
    $\begingroup$ So how about taking a finite language as a decidable?) $\endgroup$
    – Tonita
    Apr 23 at 9:57

1 Answer 1

Reset to default
6
$\begingroup$
  1. There exists undecidable languages.
  2. $A = \emptyset$ and $C = \Sigma^*$ are decidable.
  3. ????
  4. Profit.
Improve this answer
$\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.