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 enumerable
Q68. 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
Result Page:- 1-20 |
21-40 |
41-60 |
61-80 |
81-100 |
101-120 |
|
