# Union, Intersection, Difference, etc. of different types of languages

I am preparing for a competitive exam (GATE) in which questions are asked in Automata about operations among different types of languages. For example,

If $L_1$ is recursive & $L_2$ is recursively enumerable, then is $L_1\cap L_2$ recursively enumerable?

Similarly,

If $L_1$ is regular, $L_2$ is a deterministic CFL and $L_3$ is recursively enumerable, then is $L_1 \cap L_2$ a deterministic CFL? Is $L_3 \cap L_1$ recursive? Is $L_1 \cup L_2$ context free? etc.

Now I can compare such operations between languages of the same type using closure properties, but how do I tackle such questions?

• You either memorize the answers, or determine the answer on a case by case basis. In most cases either you can immediately see why the result is necessarily of type X, or it is not necessarily of type X. – Yuval Filmus Dec 29 '14 at 14:41
• Questions are never repeated in this exam. So, memorizing is useless. I need to know the exact technique of how to tackle such questions. – Shantanu Paul Dec 29 '14 at 14:48
• The technique is, try to prove that the result is of type X, and if you can't do it, try to construct a counterexample. Some practice can help you with these steps. – Yuval Filmus Dec 29 '14 at 14:50
• The answer is to understand what it means for, e.g., a language to be recursive. If you understand that, you can figure out whether the intersection/union/difference/whatever of two recursive languages is also recursive. There is no "exact proof technique". – David Richerby Dec 29 '14 at 15:34
• @Pseudonym That's already two proof techniques! (Nondeterminism and Cartesian product.) And, as you say, they don't directly apply to PDAs. – David Richerby Dec 30 '14 at 9:03