CurrentGK -> Papers -> GAT(Graduate Aptitude Test In Engineering) -> THEORY OF COMPUTATION 4

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

THEORY OF COMPUTATION 4

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





Tags


#

15 Dec, 2019, 11:19:06 AM