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