The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
2.5k 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.4k points)
edited by | 2.5k 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 (54.5k 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 ???
–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.2k points)


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

35,506 questions
42,827 answers
121,678 comments
42,181 users