The Gateway to Computer Science Excellence
+3 votes

$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


in Theory of Computation by Veteran (119k points)
retagged by | 298 views

2 Answers

+3 votes
Best answer
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 it may or may not be CFL.

so answer is A)
by Boss (17.1k points)
selected by

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


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 ..

0 votes
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!
by (473 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,388 answers
105,413 users