GATE IT 2005 | Question: 4

Question

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?

• 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

Comments

What is a non regular language? Like for which we can't write regular expression?

Answer 1

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)

Comments

Yes. Those counter example exactly makes sense and gives clear idea.

---

can it be solved by using this diagram??

---

Yes sure, it can be analyzed using this diagram. As complement of CFL gives CSL and complement of regular gives regular. So CSL union Regular is CSL.

---

@Arjun sir,

L= Regular & Compliment of regular = Regular 

 

M=CFL &Compliment of CFL is may not be context-free language,

NOW,
 (compliment of regular U compliment of CFL) = It is necessarily regular but may or may not be context-free.

can we say like this ???

---

If it is intersection than the language is regular ?

---

Ruchi Vohra

The same explanation as given in the above answer will work if it was an intersection in place of Union in the above question. 

If, \(L = \varnothing \) then \(L^c = \sum^* \) and \(M^c \;\cap \sum^* = M^c \)

We know that the complement of CFL may or may not be CFL.

\(L = \sum^* \) then \(L^c = \varnothing \)  and \(M^c \;\cap \varnothing = \varnothing \) thus a regular language.

---

Can it be said that L’ union M’ = CSL compulsorily ?

---

Yes, you are right.

---

what would be the result of Σ* U non-recursively enumerable language ?

---

@Rutuja Desai It would be $\sum ^{*}$ as any language is subset of $\sum ^{*}$.

---

Can't we consider the possibility where $L^{c}\cup M^{c} = (L\cap M)^{c}$

Then $L\cap M$ would be regular right as regular languages are subset of CFL. And complement of it would be regular as it's closed under complement.

Answer 2

D. None

Lc = Regular

MC= Not necessarily CFL

LC U MC = Not Necessarily CFL or Regular

Comments

"Not necessarily" You hit the nail on the head there- correct way to apply closure property.

But the proof is not complete for "whether union of a non CFL and a regular language is non-regular or CFL or non-CFL". To do this we need to give a counterexample for each false case.

---

It is necessarily CSL (Context sensitive language). But not necessarily Regular or CFL

Answer 3

if L is regular then L^c is also regularand and if M is context free then M should be recursive and M^C should 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)

Answer 4

M^c  is nothing but an RECURSIVE language

L^c  ∪ R (recursive language)= recursive language ;

because from the CHOMSKY HEIRARCHE every regular is an recursive .

so ,i think option D