Q57. Given the following statements :

(i) Recursive enumerable sets are closed under complementation.

(ii) Recursive sets are closed under  complementation.

Which is/are the correct statements ?

(A) only (i)

(B) only (ii)

(C) both (i) and (ii)

(D) neither (i) nor (ii)

Answer(B)

Explanation

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 Kleen star of L
• the concatination of L and P
• the union  of L and P
• the intersection of L and p.

Note that recursively enumerable languages are not closed under  set differnce 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.