1,239 views
0 votes
0 votes

If  $L_1$ is DCFL and $L_2$ is context free language. Consider the below given statements

Which is correct between these and why ? (S1 is correct.. but why ??) . I couldn’t understand the explanation given in the solution..

1 Answer

1 votes
1 votes

S1:  $\bar{L_{1}}$  - ${L_{2}}$  : True
it can be written as $\bar{L_{1}}$  $_{\bigcap }$ $\bar{L_{2}}$   , L2 is given as CFL and CFL is not closed under complementation and it will fall in 1 higher class of language CSL.

S2: $\bar{L_{1}}$  - $\bar{L_{2}}$ : False

it can be written as  $\bar{L_{1}}$  $_{\bigcap }$ ${L_{2}}$ , which is again not closed under intersection/union.

 

If L1 and L2 are CFLs, then L1 ∩ L2 may not be a CFL.

Both CFL and DCFL are closed under intersection with regular sets.

reshown by

Related questions

3 votes
3 votes
1 answer
1
logan1x asked May 10, 2019
1,106 views
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
2 votes
2 votes
2 answers
3