Explore topic-wise MCQs in Automata Theory.

This section includes 17 Mcqs, each offering curated multiple-choice questions to sharpen your Automata Theory knowledge and support exam preparation. Choose a topic below to get started.

1.

State true or false:Statement: RASP is to RAM like UTM is to turing machine.

A. true
B. false
Answer» B. false
Discussion
2.

Which of the following is not true about RASP?

A. Binary search can be performed more quickly using RASP than a turing machine
B. Stores its program in memory external to its state machines instructions
C. Has infinite number of distinguishable, unbounded registers
D. Binary search can be performed less quickly using RASP than a turing machine
E. More than two options are incorrect
Answer» E. More than two options are incorrect
Discussion
3.

RASP stands for:

A. Random access storage program
B. Random access stored program
C. Randomly accessed stored program
D. Random access storage programming
Answer» C. Randomly accessed stored program
Discussion
4.

Statement: Instantaneous descriptions can be designed for a Turing machine.State true or false:

A. true
B. false
Answer» B. false
Discussion
5.

If d is not defined on the current state and the current tape symbol, then the machine ______

A. does not halts
B. halts
C. goes into loop forever
D. none of the mentioned
Answer» C. goes into loop forever
Discussion
6.

Which of the problems are unsolvable?a) Halting problemb) Boolean Satisfiability problemc) Both (

A. Halting problemb) Boolean Satisfiability problemc) Both (a) and (
B. Boolean Satisfiability problem
C. Both (a) and (b)
D. None of the mentioned
Answer» D. None of the mentioned
Discussion
7.

WHICH_OF_THE_FOLLOWING_IS_NOT_TRUE_ABOUT_RASP??$

A. Binary search can be performed more quickly using RASP than a turing machine
B. Stores its program in memory external to its state machines instructions
C. Has infinite number of distinguishable, unbounded registers
D. Binary search can be performed less quickly using RASP than a turing machine
Answer» E.
Discussion
8.

RASP_STANDS_FOR:?$

A. Random access storage program
B. Random access stored program
C. Randomly accessed stored program
D. Random access storage programming
Answer» C. Randomly accessed stored program
Discussion
9.

State true or false:$

A.
B. true
Answer» B. true
Discussion
10.

Which among the following is incorrect for o-machines?

A. Oracle Turing machines
B. Can be used to study decision problems
C. Visualizes Turing machine with a black box which is able to decide cerain decion problems in one operation
D. None of the mentioned
Answer» E.
Discussion
11.

Which of the following are the models equivalent to Turing machine?

A. Multi tape turing machine
B. Multi track turing machine
C. Register machine
D. All of the mentioned
Answer» E.
Discussion
12.

Statement: Instantaneous descriptions can be designed for a Turing machine.

A.
B. true
Answer» B. true
Discussion
13.

If d is not defined on the current state and the current tape symbol, then the machine ______

A. does not halts
B. halts
C. goes into loop forever
D. none of the mentioned
Answer» C. goes into loop forever
Discussion
14.

The value of n if turing machine is defined using n-tuples:

A. 6
B. 7
C. 8
D. 5
Answer» C. 8
Discussion
15.

Which of the following a turing machine does not consist of?

A. input tape
B. head
C. state register
D. none of the mentioned
Answer» E.
Discussion
16.

Which of the problems are unsolvable?

A. Halting problem
B. Boolean Satisfiability problem
C. Both (a) and (b)
D. None of the mentioned
Answer» D. None of the mentioned
Discussion
17.

A turing machine that is able to simulate other turing machines:

A. Nested Turing machines
B. Universal Turing machine
C. Counter machine
D. None of the mentioned
Answer» C. Counter machine
Discussion