@Arjun Sir please solve it !!! I know (A) and (C) are true ... but not sure for (B) and (D).

The Gateway to Computer Science Excellence

+31 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?

- $L_1 \cap L_2$ is a deterministic CFL
- $L_3 \cap L_1$ is recursive
- $L_1 \cup L_2$ is context free
- $L_1 \cap L_2 \cap L_3$ is recursively enumerable

+40 votes

Best answer

- True : DCFL are closed under Intersection with Regular Languages
- 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.
- True : $L_1$ is regular hence also CFL and every DCFL is also CFL and All CFL are closed under Union.
- True : $L_1$ is regular hence also RE; $L_2$ is DCFL hence also RE; RE languages are closed under Intersection

+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.

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.

+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.

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.

+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.

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,242 answers

198,010 comments

104,604 users