The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+23 votes

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a  recursively enumerable, but not recursive, language. Which one of the following statements is false?

  1. $L_1 \cap L_2$  is a deterministic CFL
  2. $L_3 \cap L_1$  is recursive
  3. $L_1 \cup L_2$  is context free
  4. $L_1 \cap L_2 \cap L_3$  is recursively enumerable
asked in Theory of Computation by Active (3.7k points) | 2.5k views
@Arjun Sir please solve it !!! I know (A) and (C) are true ... but not sure for (B) and (D).
can regular lang. is recursive?

2 Answers

+35 votes
Best answer
  1. True : DCFL are closed under Intersection with Regular Languages
  2. False : $L_1$ is recursive hence also decidable, $L_3$ is RE but not Recursive hence it is undecidable. Intersection of Recursive language and Recursive Enumerable language is Recursive Enumerable language.
  3. True : $L_1$ is regular hence also CFL and every DCFL is also CFL and All CFL are closed under Union.
  4. True : $L_1$ is regular hence also RE; $L_2$ is DCFL hence also RE; RE languages are closed under Intersection
answered by Active (3.8k points)
edited by
@Danish, In option B , L3 is REL. L1 is regular, so L1 will also be a REL trivially. And as REL are closed under intersection, L1∩L2 will be REL. Am I right ?

also, if a language is regular, will it always be decidable.In light of this, every regular language should be Recursive as recursive languages are decidable ?  this violates option D in which we consider L1 to be REL trivially.

"L1∩L2 will be REL" but not recursive 

for option D. Recursive language is REL too 

here the b option is false because l3 here is a recursively enumereable language and l1 here is a regular language so here therefore l1 which is a regular language is also a recursively enumereable language so that when we are doing intersection of this two recursive enumereable languages we can get a recursive enumereable language as recursively enumereable languages are closure under intersection but we can not sure that it will be a recursive language.
I m not getting it

L1 is regular

L3 is RE but not REC

k fine but L1 intersection L3

we get L1 and regular language is recursive so how thiz is false.
all are right here.
Actually L3 is REL but NOT REC, means its an undecidable language and L1 is decidable, also to note that reg intersection with any language (x) is x only,

So REL intersect REG = REL wiz not REC as given in ques.
@PRAVEEN SAINI              L3  is clearly given , it  is RE BUT NOT RECCURSIVE .     L1 is reg and L2 is dcfl    that means both L1 AND L2 are  RECURSIVE           SO L3  INTERSECTION L1    WILL BE    EMPTY SET

                          ALSO L3 INTERSECTION  L2  WILL BE EMPTY SET  , THEN option B and D  both should be regular     .   this way both options will be correct.        am I right    ???  please correct me
+3 votes
L1∩L2 is a deterministic CFL because intersection of any lang. with regular is closed.

L3∩L1 is recursive is False because it should be RE {recursive enumerable not recursive}

L1∪L2 is context free is true, because every DCFL is CFL.

L1∩L2∩L3 is recursively enumerable is true.
answered by Loyal (7.4k points)
can you please explain 4th option ?
Recursive enumerable is higher set, so, L1∩L2∩L3 whatever lang. may come , we can say it is recursively enumerable.

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,526 questions
42,803 answers
42,166 users