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?


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?

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 29 '14 at 14:41
  • $\begingroup$ Questions are never repeated in this exam. So, memorizing is useless. I need to know the exact technique of how to tackle such questions. $\endgroup$ – Shantanu Paul Dec 29 '14 at 14:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 29 '14 at 14:50
  • 1
    $\begingroup$ 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". $\endgroup$ – David Richerby Dec 29 '14 at 15:34
  • 1
    $\begingroup$ @Pseudonym That's already two proof techniques! (Nondeterminism and Cartesian product.) And, as you say, they don't directly apply to PDAs. $\endgroup$ – David Richerby Dec 30 '14 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.