Tuesday 26 May 2015

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.

No comments:

Post a Comment

Note: only a member of this blog may post a comment.