GATE IT 2006 | Question: 32

Question

Let $L$ be a context-free language and $M$ a regular language. Then the language $L ∩ M$ is

• A. always regular
• B. never regular
• C. always a deterministic context-free language
• D. always a context-free language

Comments

Weather option D is NON DETERMINISTIC CFL? ??

---

option D is the correct option.

---

@Sagar78   as it is written CFL we have to consider for both DCFL and NCFL(non-deterministic).

 

Answer 1

Answer: D

Comments

I have a doubt what if we take regular language as empty set { } or phi then if we take common between CFL and regular language which is empty set then it will give empty set as final answer which regular language. So answer can be regular language also.

---

@harsh RL is a subset of CFL. Moreover, in options, we have always RL and never RL, not sometimes RL. So the only D is correct.

Answer 2

https://cs.stackexchange.com/questions/18642/intersection-of-context-free-with-regular-languages

The above link contains a very well written answer to your question with a neat and easy to understand explanation.

 

Hope it helps ! :)

Comments

Intersection of context free with regular languages and Intersection of regular languages  with  context free both are same of different??? 

---

Intersection is commutative. So, both are same.