I am trying to understand closure properties between different language classes. For example, if L1 is regular and L2 is recognisable, then is L1 intersection L2 decidable? My answer is that L1 is also recognisable and therefore L1 intersection L2 is recognisable. However, this cannot guarantee that it is decidable. Is this a correct solution?
3
-
1$\begingroup$ You are right. L1 intersection L2 is not necessarily decidable, but it is recognizable (recursively enumerable, partially computable). $\endgroup$– fade2blackCommented Jun 9, 2017 at 16:41
-
$\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher $\endgroup$– David RicherbyCommented Jun 9, 2017 at 20:32
-
1$\begingroup$ To show that $L_1 \cap L_2$ is not necessarily decidable, you need to give an example in which it isn't. $\endgroup$– Yuval FilmusCommented Jun 10, 2017 at 7:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yours is a correct intuition: $L_1 \cap L_2$ is indeed recognisable.
However, you can't say that such language is not decidable only because you failed to prove it decidable. In theory, there could be a more complex argument that you were not able to find, which could establish that $L_1 \cap L_2$ is actually decidable.
To prove it, you need a counterexample. It is usually helpful to try corner cases, first.
For instance if $L_1 = \Sigma^*$, which is regular, we get $L_1 \cap L_2 = L_2$ which is decidable only if $L_2$ is such. Hence, since recognizable but non decidable languages exist, we get a counterexample.
Further, note that if we took $L_1 = \emptyset$, which is regular, then $L_1 \cap L_2 = \emptyset$ which is decidable, whatever $L_2$ is.
Hence, from the given hypotheses, we can not conclude that $L_1 \cap L_2$ is decidable, nor that it is not. This is because we found counterexamples to both conjectures.
