2
$\begingroup$

I'm having trouble with proving that "Intersection of a recognizable language anda decidable language is decidable.

I assume this is true although I have no idea how to proof it. Can somebody point me in the right direction?

$\endgroup$

migrated from cstheory.stackexchange.com Jun 4 at 0:39

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ Looks like homework. Voting to close. $\endgroup$ – Aryeh Jun 2 at 9:53
  • $\begingroup$ It's not homework, just extra questions in our course notes to think about to understand the subject matter better. $\endgroup$ – Bobby Jun 2 at 9:57
4
$\begingroup$

It's false. Let $L_1=\Sigma^*$ be a decidable language and $L_2=L_{HALT}$ be the (recognizable) language of all halting TM-string pairs. Then $L_1\cap L_2=L_2$, which is not decidable.

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