Computer Science Engineering (CSE)  >  Theory of Computation  >  Test: Non Deterministic Turing Machines Download as PDF

Test: Non Deterministic Turing Machines


Test Description

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

Test: Non Deterministic Turing Machines for Computer Science Engineering (CSE) 2022 is part of Theory of Computation preparation. The Test: Non Deterministic Turing Machines questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Non Deterministic Turing Machines MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Non Deterministic Turing Machines below.
Solutions of Test: Non Deterministic Turing Machines questions in English are available as part of our Theory of Computation for Computer Science Engineering (CSE) & Test: Non Deterministic Turing Machines solutions in Hindi for Theory of Computation course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Non Deterministic Turing Machines | 10 questions in 10 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Theory of Computation for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
1 Crore+ students have signed up on EduRev. Have you?
Test: Non Deterministic Turing Machines - 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?

Detailed Solution for Test: Non Deterministic Turing Machines - Question 1

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

Test: Non Deterministic Turing Machines - Question 2

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

Detailed Solution for Test: Non Deterministic Turing Machines - Question 2

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

Test: Non Deterministic Turing Machines - Question 3

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

Detailed Solution for Test: Non Deterministic Turing Machines - Question 3

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.

Test: Non Deterministic Turing Machines - Question 4

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

Detailed Solution for Test: Non Deterministic Turing Machines - Question 4

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

Test: Non Deterministic Turing Machines - Question 5

Pick the odd one out.

Detailed Solution for Test: Non Deterministic Turing Machines - Question 5

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

Test: Non Deterministic Turing Machines - Question 6

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

Detailed Solution for Test: Non Deterministic Turing Machines - Question 6

 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.

Test: Non Deterministic Turing Machines - Question 7

Can a turing machine act like a transducer?

Detailed Solution for Test: Non Deterministic Turing Machines - Question 7

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.

Test: Non Deterministic Turing Machines - Question 8

Which of the following does not exists?

Detailed Solution for Test: Non Deterministic Turing Machines - Question 8

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.

Test: Non Deterministic Turing Machines - Question 9

Enumerator is a turing machine with __________

Detailed Solution for Test: Non Deterministic Turing Machines - Question 9

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.

Test: Non Deterministic Turing Machines - Question 10

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

Detailed Solution for Test: Non Deterministic Turing Machines - Question 10

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.

18 videos|44 docs|39 tests
Use Code STAYHOME200 and get INR 200 additional OFF
Use Coupon Code
Information about Test: Non Deterministic Turing Machines Page
In this test you can find the Exam questions for Test: Non Deterministic Turing Machines solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Non Deterministic Turing Machines, EduRev gives you an ample number of Online tests for practice