4k 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
| 4k views
0
@Arjun Sir please solve it !!! I know (A) and (C) are true ... but not sure for (B) and (D).
+1
can regular lang. is recursive?
0 $L_{1}\cap L_{3}=L1?$

$L_{1}\cup L_{3}=L_{3}?$

How $(B)$ is false$?$

+1

$L_1$ is regular $\implies$ ( it is recursive AND it is also recursively enumerable.) i.e. $REC\ and \ RE$

$L_3$  is not recursive AND it is recursively enumerable. i.e. $(\sim REC)\ and \ RE$

$L_1 \cap L_2 =$ common part of both $L_1$ and $L_3 = RE$

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
by Active (4k 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

+3
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.
+3
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
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.
by Loyal (7.8k 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.