Q 40,paper2,June 12.Consider the following statements :

I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.
Which of the above statements are true ?
Options (A) I only
(B) I and II
(C) I and III
(D) II and III
Answer (B) 1 and 2.
Recursively enumerable languages are closed under the following operations. That is, if L and P are two recursively enumerable languages, then the following languages are recursively enumerable as well:
• the Kleene star of L
• the concatenation of L and P
• the union
• the intersection .
Note that recursively enumerable languages are not closed under set difference or complementation. The set difference L - P may or may not be recursively enumerable. If L is recursively enumerable, then the complement of L is recursively enumerable if and only if L is also recursive.
Recursive languages are closed under the following operations. That is, if L and P are two recursive languages, then the following languages are recursive as well:
• The Kleene star • The image φ(L) under an e-free homomorphism φ
• The concatenation
• The union
• The intersection
• The complement of
• The set difference
Remember that there are three possible outcomes of executing a Turing machine over a given input. The Turing machine may
• Halt and accept the input;
• Halt and reject the input; or
• Never halt.
A language is recursive if there exists a Turing machine that accepts every string of the language and rejects every string (over the same alphabet) that is not in the language. Note that, if a language L is recursive, then its complement -L must also be recursive. (Why?) A language is recursively enumerable if there exists a Turing machine that accepts every string of the language, and does not accept strings that are not in the language. (Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop.) Clearly, every recursive language is also recursively enumerable. It is not obvious whether every recursively enumerable language is also recursive.