1 1 vote 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 Theory of Computation theory-of-computation reduction decidability + – srestha 923 views answer comment Share Follow Print See all 4 Comments 4 4 Comments reply akash.dinkar12 commented Feb 28, 2019 reply Follow flag A?? 0 0 replyShare srestha commented Feb 28, 2019 reply Follow flag yes, can u explain other option 0 0 replyShare akash.dinkar12 commented Mar 1, 2019 reply Follow flag 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.. 2 2 replyShare ankitgupta.1729 commented Mar 1, 2019 reply Follow flag @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 ? 1 1 replyShare Please log in or register to add a comment.
