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

Let $\Sigma=\{a,b\}.$
$L_1 = \Sigma^*$ is a regular language
$L_2 = \{ww^R \mid w \in (a+b)^*\}$ is a context free language.
$L_1\cap L_2 = \{ww^R \mid w \in (a+b)^*\}$  which is clearly context free language and not DCFL or Regular
Hence, the answer is option D.

Comments

$(a+b)^*$ is a regular language

$a^n b^n$ is a CFL

intersection will always be CFL Lakshman Patel RJIT

---

In closure property, there is three special cases, called as regular union,regular intersection, regular difference.

L=REG/DCFL/CFL/CSL/REC/RE

1) L ∩ REG = L        

2) L ∩ REG = L

3) L ∩ REG =L

This also can help-https://www.geeksforgeeks.org/union-and-intersection-of-regular-languages-with-cfl/

---

https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf

Answer 2

Eliminate each option by throwing a counter example

L –  Context free language, M – Regular language

A) always regular

$L$ - {$a^{n}b^{n}$}

$R$ - {$a^{*}b^{*}$}

$L \cap R$ = {$a^{n}b^{n}$}, which is not regular

Therefore, A) is False

B) Never regular

$L$ = { }

$R$ = { }

$L \cap R$ = { }, which is regular

Therefore B) is False

C)  always a deterministic context-free language

$L$ - $\left \{ ww^{r}, w\in \left \{ a,b \right \}^{*} \right \}$

$R$ - $\left \{ (a+b)^{*} \right \}$

$L \cap R$ =$\left \{ ww^{r}, w\in \left \{ a,b \right \}^{*} \right \}$, which is non-deterministic CFL

Therefore, C) is False

So, Option D is True

 

Actually, to come to a conclusion of “always correct”, you need to come up with the proof. You can’t just show one example as “correct” and come to a conclusion of “always correct”.

But you can come to a conclusion of “not always correct” by just throwing a counter example which tells as “not correct”.

Answer 3

It is always a cfl.i really never heard it to be dcfl which is less powerful than cfl

Answer 4

1. Any Language (say L1)  $ \bigcap$ Regular language = L1 always. 
2. Any language (L2) $\cup$ Regular language = L2 always 

Hence option D.