If L and P are two recursively enumerable languages, then they are not closed…

2017

If L and P are two recursively enumerable languages, then they are not closed under

  1. A.

    Kleene Star L * of L

  2. B.

    Intersection L ∩ P

  3. C.

    Union L ∪ P

  4. D.

    Set Difference

Attempted by 32 students.

Show answer & explanation

Correct answer: D

Recursively enumerable (RE) languages are closed under union, intersection, concatenation, and Kleene star. However, they are not closed under complementation or set difference. This is because the complement of an RE language is not necessarily RE (it might be recursive or neither). Since set difference involves intersecting with a complement, the result may not be RE. Therefore, RE languages are not closed under set difference.

Explore the full course: Isro