Time Left - 10:00 mins

ECIL GET 2018 : Topic wise test-2 (Theory of Computation)

Attempt now to get your rank among 574 students!

Question 1

Write the transition rule for the code
0001000100010010

Question 2

Find the true statement from the following?

Question 3

Identify the operation which is not closed for recursive languages.

Question 4

the aim of the following question is to prove that the language {M | M is the code of a
Turing Machine which, irrespective of the input, halts and outputs a 1}, is undecidable. This is to be done by reducing form the language {M’, x|M’halts on x}, which is known to be undecidable. In parts A. and B. describe the 2 main steps in the construction of M. in part C. describe the key property which relates the behaviour of M on its input w to the behavior of M’onx.
On input w, what is the first step that M must make?

Question 5

the aim of the following question is to prove that the language {M | M is the code of a
Turing Machine which, irrespective of the input, halts and outputs a 1}, is undecidable. This is to be done by reducing form the language {M’, x|M’halts on x}, which is known to be undecidable. In parts A. and B. describe the 2 main steps in the construction of M. in part C. describe the key property which relates the behaviour of M on its input w to the behavior of M’onx.
On input w, based on the outcome of the first step, what is the second step that M must Make?

Question 6

the aim of the following question is to prove that the language {M | M is the code of a
Turing Machine which, irrespective of the input, halts and outputs a 1}, is undecidable. This is to be done by reducing form the language {M’, x|M’halts on x}, which is known to be undecidable. In parts A. and B. describe the 2 main steps in the construction of M. in part C. describe the key property which relates the behaviour of M on its input w to the behavior of M’onx.
What key property relates the behaviour of M on w to the behavior of M’onx?

Question 7

If there is a reduction from problem P1 to P2
If P1 is undecidable then P2 is?

Question 8

Let G1, G2 be context-free grammars. Then L(G1) L(G2) =

Question 9

Which of the following problems is undecidable?

Question 10

Which of the following statements is false?
  • 574 attempts
  • 1 upvote
  • 7 comments
Oct 4GATE & PSU CS