Question

Class of recursively enumerable language are not closed under complementation proof

Answer 1

Answer:

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.

✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌

Answer 2

Explanation:

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.

However, the set of Turing-recognizable languages is not closed under complement. Theorem 6: The set of Turing-decidable languages is closed under union, intersection, and complement