[Solved]: Intersection of Turing-recognizable language and regular language

Problem Detail: 

True or false: An intersection of a Turing-recognizable and a regular language is always Turing-decidable.

This was asked on a practice test and the answer is False. Why? I thought regular languages were a subset of decidable languages. So if you intersect regular and recognizable the result would also have to be a subset of decidable.

Is that not correct?

Asked By : Nryan6

Answered By : David Richerby

I thought regular languages were a subset of decidable languages. So if you intersect regular and recognizable the result would also have to be a subset of decidable.

There are two confusions here.

First, your seamless switch from "decidable languages" to "recognizable" makes it sound as if you think that decidable and recognizable are the same thing: they're not.

Second, you're confusing the concept of the set of regular languages being a subset of the set of decidable languages with the concept of a particular regular language being a subset of a particular decidable language. Saying that the regular languages are a subset of the decidable languages (which is true) is just saying that every regular language is decidable: this is true. However, that doesn't tell you that every regular language is a subset of every decidable language: it tells you that every regular language is a decidable language. For example, consider $L_1 = \{a^n\mid n\geq 0\}$ and $L_2 = \{a^n\mid n\text{ is prime}\}$. $L_1$ is regular and $L_2$ is decidable but $L_1\not\subseteq L_2$. But the fact that $L_1$ is regular does tell you that $L_1$ is also decidable.

Putting these two things together gives us the following.

1. If you intersect the set of regular languages with the set of recognizable languages, you get the set of languages $$\{L\mid L \text{ is regular and }L\text{ is recognizable}\}\,.$$ Since every regular language is recognizable, this is just the set of regular languages.

2. If you intersect an individual regular language $L_1$ with an individual recognizable language $L_2$, you get the set of words $$\{w\mid w\in L_1\text{ and }w\in L_2\}\,.$$ You can prove that this is recognizable (write a recognizer for it!) but it's not necessarily decidable or regular.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49361