Let L be a regular language and M be a context-free language, both over the…
2005
Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let Lc and Mc denote the complements of L and M respectively. Which of the following statements about the language Lc∪ Mc 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
Attempted by 10 students.
Show answer & explanation
Correct answer: D
The complement of a regular language Lc is always regular because regular languages are closed under complementation. However, the complement of a context-free language Mc is not necessarily context-free; it may be recursively enumerable but not context-free. The union Lc ∪ Mc combines a regular language with potentially non-context-free language, so the result is not necessarily context-free. Since option B claims it is necessarily context-free and this is false, and options A and C make incorrect generalizations, the correct choice is D: None of the above.