The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
87 views
If $L_{1}\preceq L_{2}$ and $L_{2}$ turing recognizable

Then $L_{1}$ cannot be

A)not REL

B)Context Sensitive

C)Context Free

​​​​​​​​​​​​​​D)Recursive
asked in Theory of Computation by Veteran (114k points) | 87 views
0
A??
0
yes, can u explain other option
+1
It is already given that L2 is Turing recognizable and also we have reduction L1 reduces to L2 it means we can convert of every instance of L1 into L2 and that means L1 is also Turing recognizable and so it may/may not be CSL,CFL and recursive..
0

@akash.dinkar12 we use reduction for problems.. right ? If we write $P_{1}\preceq P_{2}$ then it means problem $P_{2}$ is atleast as hard as problem $P_{1}$ for all the instances. right ? Is language make sense here ? 

Please log in or register to answer this question.

Related questions

+5 votes
1 answer
2
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
49,434 questions
53,630 answers
186,008 comments
70,900 users