0
$\begingroup$

I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is same as $L_1$.

I thought so far that I can describe $L_2$ with a Turing machine. So I can next find the intersection Turing machine of both.

I do not know what to do about the last part of the problem. Maybe I can say that $L_2$ is decidable (because it is regular) and $L_1 \cap L_2$ is a subset of that. So it is also decidable.

I am not sure whether my approach is correct or not. Please help me.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Hint: How do you show that the intersection of two regular languages is regular? $\endgroup$
    – Raphael
    Commented Dec 4, 2014 at 11:27

1 Answer 1

Reset to default
0
$\begingroup$

The method you propose in your answer is mostly correct. $L_2$ is, indeed, decidable because it's regular. But you can't argue that $L_1\cap L_2$ is decidale because it is a subset of the decidable language $L_2$: every language is a subset of the decidable language $\Sigma^*$ but that doesn't mean that every langauge is decidable.

Hint. You chose the tag , which shows you're on the right lines. $L_1$ is either decidable or recognizable; $L_2$ is both. What do you know about the intersection of two decidable/recognizable languages?

Improve this answer
$\endgroup$
4
  • $\begingroup$ I know that intersection of two decidable is decidable and intersection of two recognizable is recognizable. What can we say about intersection of a decidable language and a recognizable language (which is not decidable)? $\endgroup$
    – binamu
    Commented Dec 4, 2014 at 8:49
  • $\begingroup$ Any language taht is decidable is also recognizable so it's enough to look at the intersection of two recognizable languages. $\endgroup$
    – David Richerby
    Commented Dec 4, 2014 at 8:57
  • $\begingroup$ In the problem, I have to prove that the decidability of the intersect is same as $L_2$. It means that if $L_2$ is recognizable but not decidable, then the intersection is also recognizable but not decidable. $\endgroup$
    – binamu
    Commented Dec 4, 2014 at 9:03
  • $\begingroup$ You have to show that it's the same as $L_1$ but I guess that was just a typo in your comment. You can't go as far as "If $L_1$ is recognizable but not decidable, $L_1\cap L_2$ is recognizable but not decidable", since $L_2$ might be the empty set, which is regular and which gives $L_1\cap L_2=\emptyset$, which is both recognizable and decidable. So the best you can do is that $L_1$ recognizable implies $L_1\cap L_2$ recognizable, and $L_1$ decidable implies $L_1\cap L_2$ decidable. $\endgroup$
    – David Richerby
    Commented Dec 4, 2014 at 9:13

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.