The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- $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

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

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

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.

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.

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.

@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.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,271 comments

38,803 users