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