edited by
3,154 views
2 votes
2 votes
What will the intersection of a recursive and recursive enumerable language.

Will it be recursive???
edited by

1 Answer

5 votes
5 votes
Let $L = \Sigma^*$ and $M$ be the language of halting problem. Now, here $L$ is recursive and $M$ is recursively enumerable but not recursive.

$L \cap M = M,$ is recursively enumerable but not recursive.

So, the intersection of a recursive and recursively enumerable language need not be recursive.

But the intersection will be recursively enumerable because every recursive language is recursively enumerable and recursively enumerable set is closed under intersection.

Related questions