## Closure-Property

 Question 1
The set of all recursively enumerable languages is
 A closed under complementation. B closed under intersection. C a subset of the set of all recursive languages. D an uncountable set.
Theory-of-Computation       Closure-Property       Gate 2018
Question 1 Explanation:
Recursive enumerable languages are closed under intersection.
Recursive enumerable languages are not closed under Complementation.
Recursive enumerable languages are a countable set, as every recursive enumerable language has a corresponding Turing Machine and set of all Turing Machine is countable.
Recursive languages are subset of recursive enumerable languages.
 Question 2

Consider the following types of languages: L1: Regular, L2: Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE?

 A I only B I and III only C I and IV only D I, II and III only
Theory-of-Computation       Closure-Property       GATE 2016 set-2
Question 2 Explanation:
I.
L3 is recursive, so is also recursive (because recursive language closed under complementation), so is recursive enumerable.
L4 is recursive enumerable.
So is also recursive enumerable (closed under union).
II.
L2 is context free, so L2 is recursive.
Since L2 is recursive. So is recursive.
L3 is recursive.
So is also recursive (closed under union)
III.
L1 is regular, so L1* is also regular.
L2 is context free.
So, L1*∩L2 is also context free (closed under regular intersection).
IV.
L1 is regular.
L2 is context free, so may or may not be context free (not closed under complement).
So, may or may not be context free.