7,686 views
40 votes
40 votes

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 $L^c\cup M^c$ is TRUE?

  1. It is necessarily regular but not necessarily context-free.
  2. It is necessarily context-free.
  3. It is necessarily non-regular.
  4. None of the above

4 Answers

Best answer
105 votes
105 votes

Take $L = Σ^*$ then $L^c =\varnothing$ and $M^c \cup \varnothing = M^c$

We know that complement of CFL need not be a CFL as CFL is not closed under complement.

So, (A) and (B) are false. 

If we take $L = \varnothing$ then $L^c = Σ^*$  and $M^c \cup Σ^* = Σ^*$ which is regular - (C) is also false.

So, answer (D)

edited by
12 votes
12 votes
D. None

Lc = Regular

MC= Not necessarily CFL

LC U MC = Not Necessarily CFL or Regular
edited by
1 votes
1 votes

if L is regular then Lis also regularand and if M is context free then M should be recursive and Mshould be recursive(not necessarily be cfl) and,  regular $\cap $ recursive is = recursive (not regular not context free).so, answer should be none of this i.e option(D)

0 votes
0 votes

M is nothing but an RECURSIVE language

L∪ R (recursive language)= recursive language ;

because from the CHOMSKY HEIRARCHE every regular is an recursive .

so ,i think option D

 

Answer:

Related questions

23 votes
23 votes
1 answer
1
Ishrat Jahan asked Nov 3, 2014
6,378 views
The language $\{0^n 1^n 2^n \mid 1 \leq n \leq 10^6\}$ isregularcontext-free but not regularcontext-free but its complement is not context-freenot context-free