2.7k views

Multiple choices may be correct:

If $L1$ is context free language and $L2$ is a regular language which of the following is/are false?

1. $L1-L2$ is not context free

2. $L1 \cap L2$ is context free

3. $\sim L1$ is context free

4. $\sim L2$ is regular

edited | 2.7k views

$L_2$ is regular, so complement of $L2, ( \sim L2)$, is also regular .

Regular languages under complement. So, D is  True.

$L_1 \cap L_2$ is context free.

Intersection of Context free language with Regular language is Context free.  So, B is True.

$L_1 - L_2 = L_1 \cap (\sim L_2)$  is context free

Intersection of Context free language with Regular language is Context free.  So, A is  False .

$\sim L_1$ is not context free

Context free languages are not closed under complement.  So C is False  (May/not be).

edited
0

Sir I'm having a doubt in option B . As every regular language is also a CFL so intersection of L1 and L2 will imply intersection of two context free languages. as the CFLs are not closed under intersection, so this should  not necessarily be a CFl. ??

0
Not closed mean ??

It mean it may or may not be CFL.
0
Yes, thats what I'm saying. L1 intersection L2 may or may not be a CFL. So why is option B always true ?
0
Oh I am sorry, mistaken your question.

but Intersection of CFL with regular language is closed.
0
This kind of questions can also be answered using ven diagram ..... right ???

L1 : CFL , L2 : RL
option A : L1-L2
=L1∩(∼L2)
=CFL∩(∼RL)
=CFL∩(RL) ( as RL is closed under complementation )
=CFL∩CFL ( as if lang is RL then it is CFL also )
may be CFL or not ( as CFL is not closed under intersection)
hence option A statement may be false may not be ( here nothing mentioned about "ALWAYS")
option B : same logic as option A
hence option B statement may be false may not be
option C : CFL is not closed under intersection so we cant say anthing about it whether it is CFL or not
option D : True as RL is closed under complementation

but question asking about FALSE statements ( all given options are TRUE)
so Ans is None

verify this

0
what is the meaning of closed in such type of questions