edited by
11,466 views
29 votes
29 votes

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 by

2 Answers

Best answer
44 votes
44 votes

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

Regular languages are closed 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 by
–4 votes
–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

Answer:

Related questions

54 votes
54 votes
3 answers
1
Kathleen asked Sep 23, 2014
15,413 views
A certain processor supports only the immediate and the direct addressing modes. Which of the following programming language features cannot be implemented on this proces...
35 votes
35 votes
4 answers
2
Kathleen asked Sep 23, 2014
8,962 views
The main difference(s) between a CISC and a RISC processor is/are that a RISC processor typicallyhas fewer instructionshas fewer addressing modeshas more registersis easi...
37 votes
37 votes
5 answers
3
Kathleen asked Sep 23, 2014
14,997 views
Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function?XOR gates, NOT gates$2$ to $1$ multiplexersAND gates, XOR gatesT...