Given the following statements : (A) A class of languages that is closed under…
2017
Given the following statements :
(A) A class of languages that is closed under union and complementation has to be closed under intersection.
(B) A class of languages that is closed under union and intersection has to be closed under complementation.
Which of the following options is correct ?
- A.
Both (A) and (B) are false.
- B.
Both (A) and (B) are true.
- C.
(A) is true, (B) is false.
- D.
(A) is false, (B) is true.
Attempted by 94 students.
Show answer & explanation
Correct answer: C
Answer: (A) is true, (B) is false.
Explanation:
Why statement (A) is true: Using De Morgan's law, for any two languages L1 and L2, L1 ∩ L2 = complement(complement(L1) ∪ complement(L2)). If a class is closed under complementation and union, it contains complement(L1), complement(L2), their union, and the complement of that union, so it contains L1 ∩ L2.
Why statement (B) is false: Give a counterexample. Consider the class of all finite languages over an alphabet. Finite languages are closed under union (union of finitely many finite sets is finite) and closed under intersection, but the complement of a finite language is co-finite (usually infinite) and thus not finite. Therefore this class is not closed under complementation, so closure under union and intersection does not force closure under complementation.
Conclusion: (A) is true and (B) is false.
A video solution is available for this question — log in and enroll to watch it.