GATE CSE 2021 Set 2 | Question: 12

Question

Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free?

• A. $L_1 \cap \overline{L_2} \\$
• B. $\overline{\overline{L_1} \cup \overline{L_2}} \\$
• C. $L_1 \cup (L_2 \cup \overline{L_2}) \\$
• D. $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$

Answer 1

Correct Answer: B,C,D

---

Some insights beforehand:

• CFLs are Not Closed under Intersection:
  $L_1=\{a^nb^*c^n\},L_2=\{a^nb^nc^*\}$ , $L_1\cap L_2=\{a^nb^nc^n\}$ not a CFL
• CFLs are Closed under Union:
  Let both of these CFLs be represented using grammars with start symbols $S_1$ and $S_2$ respectively. We define a new symbol $S^{’}$ such that $S^{’}\to S_1\mid S_2.$ Note: the resulting language may or may not be deterministic but will be context-free.
• CFLs are Not Closed under Complementation:
  $L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$
  We know that CFLs aren’t closed under intersection but is closed under union. So it must be the case that CFLs aren’t closed under complementation.
  Example: $L=\{a^nb^nc^n\}$ not a CFL(a CSL) but, $\overline{L}$ is and in-fact can be solved using a NPDA (construct a NPDA where it checks for either $\text{Number}_a \neq \text{Number}_b$ or $\text{Number}_b\neq \text{Number}_c$ or $\text{Number}_a \neq \text{Number}_c.$ But we can’t construct one which can check $\text{Number}_a = \text{Number}_b = \text{Number}_c)$
• Intersection or Union of a CFL and RL always gives a CFL. So it is closed under the same.

---

Now,

• A. $L_2$ is complemented so, needn’t be a CFL.
• B. $\overline{\overline{L_1}\cup\overline{L_2}}=L_1\cap L_2$ intersection of a CFL and RL is a CFL
• C. $L_1\cup(L_2\cup\overline{L_2})=L_1\cup(\Sigma^*)=\Sigma^*$  hence a CFL.
• D. $(L_1\cap L_2)\cup(\overline{L_1}\cap L_2)=L_2$  or it’s a union of two CFLs if you don’t bother to solve.

Comments

A set is closed under an operation, not the other way around

---

Yes indeed, it was a poor choice of words. I’d improved the answer now...

---

@Kanwae Kan @Arjun In option C how can we say  Σ∗  is anything other than  Σ∗ (i.e. CFL)?

---

Read more about Chompsky Hierarchy, in general RL$\subset$CFL$\subset$CSL$\subset$RecEL$\subset$RecL. Since, $\Sigma^*$$\subset$RL then, it must be also a CFL.

Happy Solving!

---

Thanks for your reply! Can you please shed some light on how Σ∗⊂RL⊂CFL⊂CSL⊂RecL⊂REL, not RL⊂CFL⊂CSL⊂RecL⊂REL ⊂ Σ∗ ? – Actually this is what I wanted to ask. I’m a little confused about the proper reasoning here.

---

Grammars differ in the ability of their automaton to distingusih whether a string belongs to the language or not. Languages here, for the most part, represent a subset of strings in $\Sigma^*$. And, each grammar has it’s own set of associated languages identifiable by it CFGs has CFLs and similarly RGs have RLs. And, some grammars can be more expressive than others which is why the subset.

For example, language $\{a^nb^n\}\subset CFLs$ not $RL$. From your question, I assume you haven’t learned about grammars and their expressive powers.

Read more about Chompsky hierarchy, Grammars and their automatons.

---

I definitely will. Thanks for your reply and suggestion!

---

L1 intersection L2’ is equivalent to L1 – L2. So, if we see from the context of the Venn diagram, where we can see regular languages are a subset of CFL. L1 is RL and L2 is CFL, as every CFL is RL too, so doing RL – CFL =  phi (null string)  and phi is a regular language, so as it’s regular, hence it’s CFL too. So, why option (A) isn’t CFL?

In option (C), how L2 union L2’ gives sigma* ?

as from what I know is L2’ means apart from CFL (as CFL is removed, so RL is also removed). So sigma* won’t be able to consider sigma* but the twist is that those RL which are ignored earlier, that would be covered by CSL or TM. So, L2 union L2’ gives sigma*. As sigma* is RL, and thus it’s CFL too. According to me, all are CFL.

Please help me prove why option A isn’t CFL?

---

I believe you need to study further about grammar and languages. Languages such $RLs, CFLs, CSLs, RELs, RLs$, differ in the ability to discern a subset of $\sum^*$.

A $CFL$ is a subset of $\sum^*$ that can be discerned a $CFG$ and its automaton; sure, some languages that a $ CFG$ expresses can be represented by an $RG$ but not all.

$CFLs\not\in RLs$. But $RLs\in CFLs$, The question doesn’t want to work out a specific case. It wants you to verify the option generically to work for any language with the given constraints.

Also $\sum^*$ isn’t $RL$. Regular Languages is a set of languages that $ RG$ can express.

---

Yes, I know that not all CFL can be represented using regular grammar, that’s the reason we have CFG which is used for CFL which can’t be generated using regular grammar. 

https://gateoverflow.in/3748/Gate-it-2005-question-4?show=3898#a3898

https://gateoverflow.in/357528/Gate-cse-2021-set-2-question-12?show=357579#a357579

https://cs.stackexchange.com/questions/63466/how-do-you-prove-sigma-star-is-regular

Here, after reading I understood that sigma* is regular. I am not able to find any references to state sigma* isn’t regular. In sigma* basically all the languages are possible, which does contain RL,CFL, etc so basically these are subsets, that I understood from you. In option A, we are removing CFL from RL, so as you said RL belongs to CFLs which means every RL is CFL, right? So, if we remove CFLs itself then we are left with RL belonging to an empty string, RL can have an empty string, it becomes an empty string that belongs to an empty string, which is true. So, aren’t we getting an empty string at the end? And the empty string is regular too.

http://www.cs.toronto.edu/~ylzhang/csc236/files/lec09-regex.pdf (pg. 27)

Please let me know where I am getting wrong.

---

Taking a complement(the set subtraction you'd mentioned) of a CFL doesn't necessarily imply the resultant will be a CFL. The proof is in the answer. Assume $L_1$ to be $\sum^*$, and $L_2$ to be a CFL whose complement is not a CFL, and it'll work out fine.

---

I read the references and came with this approach. Please let me know whether it's the right or wrong way. We know that the intersection of RL, DCFL, CFL, CSL, REC, RE with RL is closed. We have L2 which is CFL here, but as in option A it's L2', that's why we may have L2' as CFL or non-CFL as CFL's are not closed under complementation. As here we might have at least 1 condition which may not be CFL that's why say that L2' is CSL for a particular case then CSL intersection with regular will give CSL as CSL are closed under intersection with RL. So, we might have non-CFL as result, hence option A is an incorrect option. Can we prove option A is incorrect like this?

---

You figured it out! Noice! And it’s the way to prove it generically.

---

Kanwae Kan

in option A it is asking for L1 intersection L2(comp)...so even if we take reg intersection CSL then we may either get  phi  or some language which will be regular ..so in both the cases we are getting the language as CFL..so why it is incorrect option??

explain this pls!

---

@Kanwae Kan  @ankit3009

 in option 1^st     L1 intersection comp(L2)   i.e. regular intersection with context sensitive or higher language is NULL. But NULL or phi is CFL 

---

@rish1602 Bro, read the answer and discussion again if you have already read. You will get it clear. Even I was struggling with similar doubt as yours. Your doubt is obvious because a few concepts are incorrect. Read it, your doubts will be clear.

---

But still i think the question should be more clear...I mean there is still ambiguity in the question

---

Yes, I lost my 2 marks due to the ambiguous nature of the question.

---

CSL intersection with regular give CSL?? How this statement can be true.

---

What it should be according to you ?

---

It's correct according to me as well. What I all wanted is a bit more detail.

Like, we need to find an intersection of regular with CSL. So we can explain it like:

Since regular language is a subset of CSL, therefore we can replace regular with CSL.

Now, we are left with finding the intersection of CSL with CSL but we know that CSL is closed under intersection, so the Intersection of CSL with CSL is CSL.

Let me know if there is something wrong in my eplanation??

---

Seems fine to me @`JEET 

---

@Kanwae Kan

The option B which you explained in the solution is not matching with the option B of question.

kindly check once!

---

lol :’)

---

Kanwae Kan

Now perfect👍

---

NICE

Answer 2

The options should be $b,c,d$. 

Options –

(a) The Complement of CFL is Recursive. The intersection of Recursive and Regular is Recursive.

(b) It is $L_1 \cap L_2$ and intersection of CFL and regular is CFL.

(c) It is $\Sigma^*$ itself as $L_2  \cup \bar{L_2}$ is $\Sigma^*$ and union of $\Sigma^*$ and $L_1$ is $\Sigma^*$ which is regular and thus CFL.

 (d) Solving this you will get $L_2$ which is CFL. See the image below.

We can write the $(d)$ option as,

$= (23 \cap 34) \cup (14 \cap 34)$

$= (3) \cup (4)$

$= L_2$

Comments

in option D both are CFL ( regular intersection with CFL)   union of two CFL is CFL

---

The intersection of Recursive and Regular is Recursive.

How??

Is this because Regular language is a subset of Rec. language and therefore, regular language can be written as Recursive language, and hence we can say intersection of recursive language with recursive langauge is recursive(since, recursive languages are closed under intersection.)

---

@`JEET Sir,

Yes , that’s  the exact reason.