Test: Non Deterministic Turing Machines


10 Questions MCQ Test Theory of Computation | Test: Non Deterministic Turing Machines


Description
This mock test of Test: Non Deterministic Turing Machines for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 10 Multiple Choice Questions for Computer Science Engineering (CSE) Test: Non Deterministic Turing Machines (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: Non Deterministic Turing Machines quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: Non Deterministic Turing Machines exercise for a better result in the exam. You can find other Test: Non Deterministic Turing Machines extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.
QUESTION: 1

X is a simple mathematical model of a computer. X has unrestricted and unlimited memory. X is a FA with R/W head. X can have an infinite tape divided into cells, each cell holding one symbol.Name X?

Solution:

Turing machine is known as universal computer. It is denoted by M=(Q,Σ,Ґ ,δ ,q0, B,F)

QUESTION: 2

Which of the following is/are not an application of turing machine?

Solution:

A turing machine can have many applications like : Enumerator (A turing machine with an output printer), function computer, etc.

QUESTION: 3

State true or false:Statement: Turing Machine can change symbols on its tape, whereas the FA cannot change symbols on tape.

Solution:

The following mentioned is the difference between 2-way FA and TM. Another instance is that TM has a read/write tape head while FA doesn’t.

QUESTION: 4

Which of the following cannot be a possibility of a TM while it processes an input?

Solution:

The following mentioned are the only possibilities of operating a string through a turing machine.

QUESTION: 5

Pick the odd one out.

Solution:

Except Recursion, all the other options are techniques of Turing Machine construction which further includes, Checking off symbols and Storage in finite control.

QUESTION: 6

Which among the following is not true for 2-way infinte TM?

Solution:

 All of the mentioned are correct statements for a two way infinite tape turing machine. Theorems say the power of such a machine is in no way superior than a standard turing machine.

QUESTION: 7

Can a turing machine act like a transducer?

Solution:

A turing machine can be used as a transducer. The most obvious way to do this is to treat the entire non blank portion of the initial tape as input, and to treat the entire blank portion of the tape when the machine halts as output.

QUESTION: 8

Which of the following does not exists?

Solution:

If the tape contains k-dimentional array of cells infinte in all 2k directions, for some fixed k and has a finite control, the machine can be called Multidimentional TM.

QUESTION: 9

Enumerator is a turing machine with __________

Solution:

Here, the turing machine can use the printer as an output device to print strings.
Note: There is no input to an enumerator. If it doesn’t halt, it may print an infinite set of strings.

QUESTION: 10

For the following language, an enumerator will print:L={anbn|n>=0}

Solution:

An enumerator is a turing machine with an output printer. It can use an printer as an output device to print output strings. As n also holds the value , epsilon will also be a part of the output set.

Related tests