Let L be a regular language and M be a context-free language, both over the alphabet Sigma. Let L' and M' denote the complements of L and M respectively. Which of the following statements about the language L' union M 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.
GATE 2005 · Theory of Computation · Identify Class Language · medium
Answer: B. It is necessarily context-free.
Complement of L: L is regular. Regular languages are closed under complement. Therefore L' is also regular. Since every regular language is CFL, L' is also a CFL.
Union L' union M: L' is regular (hence CFL) and M is CFL. CFL is closed under union. Therefore L' union M is necessarily CFL.
Check each option: A. Not necessarily regular — M itself may not be regular (e.g., M = {a^n b^n}), and union with L' may not regularize it. FALSE.
B. Necessarily CFL — proven above. TRUE.
C. Not necessarily non-regular — if L and M are both regular, L' union M is regular. FALSE.
D. Not 'none of the above' since B is true. FALSE.