GATE 2005-IT

Question 4

Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let L^c and M^c denote the complements of L and M respectively. Which of the following statements about the language if L^c ∪ M^c is TRUE?

A	It is necessarily regular but not necessarily context-free.
B	It is necessarily context-free.
C	It is necessarily non-regular.
D	None of the above.

Theory-of-ComputationRegular Languages and finite automata

Question 4 Explanation:

Context-free languages not closed under complementation. So, L^c ∪ M^c is neither regular nor context-free. It might be context sensitive language.

Correct Answer: D

Question 4 Explanation:

Context-free languages not closed under complementation. So, L^c ∪ M^c is neither regular nor context-free. It might be context sensitive language.