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

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.8k views
0
@Arjun Sir please solve it !!! I know (A) and (C) are true ... but not sure for (B) and (D).
0
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.9k points)
edited by
+2
@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.
+1

"L1∩L2 will be REL" but not recursive 

for option D. Recursive language is REL too 

+2
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.
0
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.
0
all are right here.
+1
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.
0
@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.5k points)
0
can you please explain 4th option ?
0
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

40,993 questions
47,622 answers
146,898 comments
62,346 users