toc

Question

$L1$ is a Context free language (CFL),  $L2$ is a Deterministic Context free language (DCFL)

and , $L = L1 \cap\overline{L2}$

then $L$ is

a) Need not be CFL

b) not CFL

c)DCFL

Answer 1

L2 = DCFL , which is closed under complement so L2' = DCFL

L1 = CFL ,

L = CFL ∩ (DCFL )' = CFL ∩ DCFL  BUT ,DCFL AND CFL both are not closed in intersection ...so it may or may not be CFL.

so answer is A)

http://gatecse.in/wiki/Closure_Property_of_Language_Families

Comments

@Sonam I agree. and also ur ans is correct. But my confusion is "DCFL AND CFL both are not closed in intersection"

right?

So, it should be not CFL

why u told that it may CFL?

what is that "may " case I want to know

---

not closed means if we perform operation then they might be in or may not .... we cant conclude that it always not in cfl or dcfl whatever ..thats we here option A) is correct ...

if i got any eg i will tell you ..

---

ok

Answer 2

i guess language which is not in dcfl than it cannot be even in cfl so
ans is (b)
  from expressive power theory   
correct me!