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.

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

1 Answer 1

6
$\begingroup$
  1. There exists undecidable languages.
  2. $A = \emptyset$ and $C = \Sigma^*$ are decidable.
  3. ????
  4. Profit.
$\endgroup$

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.