MCQ Computer Science

# Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-32

1. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:
a) PSPACE
b) NPSPACE
c) EXPSPACE
d) None of the mentioned

### View Answer

Answer: a
Explanation: PSPACE is the problem class which contains all set of decision problems which can be solved using a turing machine taking polynomial amount of space.

2. Which of the following problems do not belong to Karp’s 21 NP-complete problems?
a) Vertex Cover problems
b) Knapsack
c) 0-1 integer programming
d) None of the mentioned

### View Answer

Answer: d
Explanation: There exists a set of 21 problems that are NP-complete and the set is called Karp’s 21 NP-complete problems.

S
3. A generalization of P class can be:
a) PTIME
b) DTIME
c) NP
d) None of the mentioned

### View Answer

Answer: c
Explanation: P is a specific case of NP class, which is the class of decidable problems decidable by a non deterministic turing machine that runs in polynomial time.

4. Which of the following are incorrect options?
a) Informally, problem is a yes/no question about an infinite set of possible instances
b) Formally, a problem is a language
c) Both (a) and (b)
d) None of the mentioned

### View Answer

Answer: d
Explanation: Example: Does a graph G has a Hamilton cycle?
=>Each undirected graph is an instance of Hamilton cycle problem.

5. Which of the following can be used to simulate any turing machine?
a) Finite State Automaton
b) Universal Turing Machine
c) Counter machines
d) All of the mentioned

### View Answer

Answer: b
Explanation: The computational aspect of any possible real world computer can be simulated using an Universal Turing Machine so can be any turing machine.

6. State true or false:
Statement: Using a two track tape, we can use a semi infinite tape to simulate an infinte tape.
a) true
b) false

### View Answer

Answer: true
Explanation: A TM with a semi-infinite tape means that there are no cells to the left of the initial head position. A TM with a semi infinite tape simulates a TM with an infinite tape by using a two-track tape.

7 Which among the following is not true for 2-way infinte TM?
a) tape in both directions
b) Leftmost square not distinguished
c) Any computation that can be performed by 2-way infinite tape can also be performed by standard TM.
d) None of the mentioned

### View Answer

Answer: d
Explanation: 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.

8. Can a multitape turing machine have an infinte number of tapes?
a) Yes
b) No

### View Answer

Answer: b
Explanation: One needs a finite number of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.

9. Which of the following is/are not true for recursively ennumerable language?
a) partially decidable
b) Turing acceptable
c) Turing Recognizable
d) None of the mentioned

### View Answer

Answer: d
Explanation: In automata theory, a formal language is called recursively ennumerable language or partially decidable or semi decidable or turing acceptable or turing recognizable if there exists a turing machine which will ennumerate all valid strings of the language.

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

### View Answer

Answer: d
Explanation: In theoretical computer science, the random access stored program( RASP ) machine model is an abstract machine used for the purpose of algorithm development and algorithm complexity theory.

11. Fill in the blank with the most appropriate option.
Statement: In theory of computation, abstract machines are often used in ___________ regarding computability or to analyze the complexity of an algorithm.
a) thought experiments
b) principle
c) hypothesis
d) all of the mentioned

### View Answer

Answer: d
Explanation: A thought experiment considers some hypothesis, theory or principle for the purpose of thinking through its consequences.
12. State true or false?
Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?
The given problem is P-complete.
a) true
b) false

### View Answer

Answer: a
Explanation: If we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so every other problem in P.
13 Which of the functions are not performed by the turing machine after reading a symbol?
a) writes the symbol
b) moves the tape one cell left/right
c) proceeds with next instruction or halts
d) none of the mentioned

### View Answer

Answer: d
Explanation: After the read head reads the symbol from the input tape, it performs the following functions:
a) writes a symbol(some model allow symbol erasure/no writing)
b) moves the tape left or right (some models allows no motion)
c) proceeds with subsequent instruction or goes either into accepting halting state or rejecting halting state.
14. The value of constants like p and e can be calculated in:
a) polynomial time
b) non-polynomial time
c) cannot be calculated
d) none of the mentioned

### View Answer

Answer: a
Explanation: The value of such constants can be calculated using algorithms which have time complexity in terms if O(nk) i.e polynomial time.
15. Which of the following statements are undecidable?
For a given Turing Machine M,
a) does M halt on an empty input tape
b) does M halt for anly inputs at all?
c) is L(M) regular? Context free? Turing decidable?
d) all of the mentioned

### View Answer

Answer: d
Explanation: All of the following mentioned are immediate results of Rice’s theorem and thus, undecidable.