+12 votes
2.3k 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

asked
edited ago | 2.3k views

## 2 Answers

+22 votes
Best answer

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

answered by Veteran (55.2k points)
edited ago by

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

Not closed mean ??

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

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

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

answered by Active (2.3k points)

+18 votes
2 answers
1
+19 votes
2 answers
2
+6 votes
2 answers
3