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

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

Which of the following CANNOT be true?

Which of the following CANNOT be true?

Which of the following CANNOT be true?

Which of the following CANNOT be true?

Which of the following CANNOT be true?

Which of the following CANNOT be true?

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?

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?

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?

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?

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?

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?

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?

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?

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?

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?

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?

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?

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?

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?

## Related Posts

Current Affairs