The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
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

asked in Theory of Computation by Veteran (59.5k points)
edited by | 2.7k views

2 Answers

+24 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 (55k points)
edited by
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 ???
–4 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)
0
what is the meaning of closed in such type of 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

38,079 questions
45,572 answers
132,069 comments
49,045 users