Question

The intersection of a context free language  and a regular language

a)need not be regular

b)need not be context free

c) is always regular

d) is always  context free

Answer 1

• $a^nb^n \cap \phi = \phi$ which is regular, so option D). is true as it is regular $\Rightarrow$ CFL
• $a^nb^n \cap \Sigma * = a^nb^n$ which is DCFL, hence option C). is false.
• The above intersection shows that we can get the result CFL, but not regular. THis actually makes option A). also true as need not be regular means that atleast on one case it is not regular .
• Hence, option D). and A). both are true .

Comments

@DD

which part ?

---

@Kapil Your second example shows the result can be DCFL but not regular. This actually makes option A true. "need not be" regular means at least on one case result is not regular.

---

Yes option a and d would be both correct

Answer 2

Intersection of any language (Regular , DCFL , CFL , CSL , RC , RE) with Regular language is definitely closed.

Regular INTERSECT Regular -------- Regular

DCFL  INTERSECT Regular----------- DCFL

CFL  INTERSECT Regular----------  CFL

CSL   INTERSECT Regular ----------CSL

Recursive INTERSECT Regular --------- Recursive

Recursively Enumerable  INTERSECT Regular --------- Recursively Enumerable
------------------------------------------------------------------------------

According to this information , I think Option D is best....

Comments

Similarly we know that If we Intersection of any language (Regular , DCFL , CFL , CSL , RC , RE) with Regular language then its result will be that particular language with which we are taking intersection

How you know this? I'm not saying this is false but the statement is not trivial.

Also, how are you taking option A false? For exams like GATE, you must be sure all other options are wrong.

---

Ok sir thanx,,, I understood...... I have to sure for all the options...

---

Does it work the same way for Union, Difference, Intersection. Like these set operations with Regular Language produces that language itself.

Answer 3

As we know

• Every Regular Language is Context Free Language
• But every Context Free Language needs not always to be Regular Language

so OPTION C IS CORRECT

---

---

---

---

Answer 4

CFL INTERSECTION RL = CFL

as CFL is closed under this.

D option