If you find this context important and usefull. We request to all visitors to sheare this with your friends on social networking channels.

THEORY OF COMPUTATION 4

# Q61. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 e P and L2 is accepted by a deterministic push down automata b) L1e NP and L2e P c) L1 is undecidable and L2 is decidable d) L1 is recursively enumerable and L2 is accepted by a deterministic linear bounded automata Q62. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 e P-SPACE and L2 is in NSPACE(2^2^2^2^n) b) L1e NP and L2e P c) L1 is undecidable and L2 is decidable d) L1 is recursively enumerable and L2 is finite Q63. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 is finite and L2 is context-free b) L1e NP and L2e NP c) L1 is undecidable and L2 is decidable d) L1 is recursively enumerable and L2 is recursive Q64. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 e P and L2 finite b) L1e NP and L2e P c) L1 is undecidable and L2 is decidable d) L1 is recursively enumerable and L2 is recursive Q65. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 e context-free and L2 regular but not finite b) L1e NP and L2 is accepted by a deterministic turing machine c) L1 is undecidable and L2 is decidable d) L1 is recursively enumerable and L2 is recursive but not context-sensitive Q66. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 is finite but not necessarily regular and L2 is context-free but not necessarily context-sensitive b) L1e NP and L2e P c) L1 is undecidable and L2 is decidable d) L1 is recursively enumerable and L2 is recursive but not necessarily context-sensitive Q67. Define languages L0 and L1 as follows: L0={<M,w,0>|M halts on w} L1={<M,w,1>| M does not halt on w} Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component w, is a string and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerableQ68. Define languages L0 and L1 as follows: L0={<M,0>|M halts} L1={<M,1>| M does not halt } Here <M,I> is a pair whose first component, M is an encoding of a turing machine starting with blank tape, second component is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q69. Define languages L0 and L1 as follows: L0={<M,w,0>|M halts on w} L1={<M,w,1>| M does not halt on w} Here <M,w,I> is a triplet, whose first component, M is an encoding of a 1200 push down tape machine , second component w, is a string representing the input, and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q70. Define languages L0 and L1 as follows: L0={<M,0>|M accepts at least two strings} L1={<M,1>| M does not accept at least two strings} Here <M,I> is a pair, whose first component, M is an encoding of a turing machine , second component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q71. Define languages L0 and L1 as follows: L0={<M,0>|M accepts an infinite set} L1={<M,1>| M does not accept an infinite set} Here <M,I> is a pair, whose first component, M is an encoding of a turing machine , second component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q72. Define languages L0 and L1 as follows: L0={<M,w,0>|M halts on w} L1={<M,w,1>| M does not halt on w} Here <M,w,I> is a triplet, whose first component, M is an encoding of a three counter machine machine , second component w is a triplet giving the initial position of the pebbles, is a string and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q73. Define languages L0 and L1 as follows: L0={<P,w,0>|P halts on w} L1={<P,w,1>| P does not halt on w} Here <P,w,I> is a triplet, whose first component, P is an encoding of a C++ program, second component w, is a string and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q74. Define languages L0 and L1 as follows: L0={<Q,w,0>|Q halts on w} L1={<Q,w,1>| Q does not halt on w} Here <Q,w,I> is a triplet, whose first component, Q is an encoding of a java program, second component w, is a string and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q75. Define languages L0 and L1 as follows: L0={<M,w,0>|M halts on w} L1={<M,w,1>| M does not halt on w} Here <M,w,I> is a triplet, whose first component, M is an encoding of a multidimentsional, multiheaded, multitape turing machine , second component w, is a string and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q76. Define languages L0 and L1 as follows: L0={<M,w,0>|M halts on w} L1={<M,w,1>| M does not halt on w} Here <M,w,I> is a triplet, whose first component, M is an encoding of a nondeterministic 789 pushdown tape machine , second component w, is a string and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q77. Define languages L0 and L1 as follows: L0={<M,w,0>|M accepts on w} L1={<M,w,1>| M does not accept w} Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component w, is a string and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q78. Define languages L0 and L1 as follows: L0={<P,w,0>|P halts on input w} L1={<P,w,1>| P loops on input w} Here <P,w,I> is a triplet, whose first component, P is an encoding of a C program, second component w, is a string and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q79. Define languages L0 and L1 as follows: L0={<M,M1,0>|M is equivalent to M1} L1={<M,M1,1>| M is not equivalent to M1} Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a turing machine, and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable Q80. Define languages L0 and L1 as follows: L0={<M,M1,0>|M accepts a subset of what is accepted by M1} L1={<M,M1,1>| M does not accept a subset of what is accepted by M1} Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a turing machine, and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerable

## Tags

#

Current Affairs
♦ PRAGATI प्‍लेटफार्म एक _____________ स्तरीय प्रणाली है। » 3
♦ अंतर्राष्ट्रीय शिक्षा दिवस कब मनाया गया? » 24 जनवरी
♦ अंतर्राष्ट्रीय शिक्षा दिवस कब घोषित किया गया था? » 3 दिसंबर, 2018
♦ भारत-पाकिस्तान युद्ध कब स्थापित किया गया था? » 1965
♦ शिक्षा का अधिकार भारतीय संविधान के ____________ में डाला गया था » अनुच्छेद 21-ए
♦ ऑपरेशन शरद हवा कब खत्म हुआ? » 27 जनवरी, 2021
♦ शिक्षा का अधिकार ____________ आयु वर्ग के बच्चों के लिए एक बुनियादी अधिकार है। » 6 से 14
♦ मानव अधिकारों की सार्वभौमिक घोषणा के ____________ में शिक्षा का अधिकार शामिल है। » अनुच्छेद 26
♦ पेरियार टाइगर रिजर्व कहाँ स्थित है? » केरला
♦ नवंबर 2020 तक, भारत की स्थापित सौर ऊर्जा क्षमता ____________ है » 36.9 GW