# Automata Theory Multiple Choice Question & Answers (MCQs) set-8

1. The class of recursively ennumerable language is known as:

a) Turing Class

b) Recursive Languages

c) Universal Languages

d) RE

### View Answer

Explanation: RE or recursively ennumerable is only called the class of recursively ennumerable language.

2. A multitape turing machine is ________ powerful than a single tape turing machine.

a) more

b) less

c) equal

d) none of the mentioned

### View Answer

Explanation: The multitape turing machine model seems much powerful than the single tape model, but any multi tape machine, no matter how many tapes, can be simulated by single taped TM.

3. State true or false:

Statement: Multitape turing machine have multi tapes where each tape is accessed with one head.

a) true

b) false

### View Answer

Explanation: Multitape turing machines do have multiple tapes but they they are accessed by separate heads.

a) Enters accepting state

b) Enters non-accepting state

c) Enters infinite loop and never halts

d) None of the mentioned

### View Answer

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

a) Finite Automaton

b) Turing Machine

c) Push down Automaton

d) None of the mentioned

### View Answer

Explanation: Linear Bounded Automaton is a type of Turing Machine where tape is not allowed to move off the portion of the tape containing the input. It is a Turing machine with limited amount of memory.

6. State true or false:

Statement: Inorder to show something is Turing complete, it is enough to demonstrate that it can be used to simulate some Turing complete system.

a) true

b) false

### View Answer

Explanation: Yes it is. For instance, an imperative language is called Turing complete if it tends to have conditional branching and an ability to maintain an arbitrary number of symbols.

A={(M,w)|M is a turing machine that accepts string w}

a) A concrete undecidable problem

b) A is recognizable but not decidable

c) -A is not recognizable

d) All of the mentioned

### View Answer

Explanation: We can proof A to be undecidable using the contradiction method.

a) TMs that always halt are known as Decidable problems

b) TMs that are guaranteed to halt only on acceptance are recursive ennumerable.

c) Both (a) and (b)

d) None of the mentioned

### View Answer

Explanation: There are two types of TMs on the basis of halting: Recursive and Recursively Ennumerable(TM may or may not halt,could loop forever).

a) polynomial

b) non polynomial

c) logarithmic

d) none of the mentioned

### View Answer

Explanation: Example: Runtimes of efficient algorithms

O(n), O(nlogn), O(n3log2n)

Runtimes of inefficient algorithms

O(2n), O(n!)

a) C is undecidable if C is reducible to B

b) C is undecidable if B is reducible to C

c) C is decidable if A is reducible to C

d) C is decidable if C is reducible to B’s complement.

### View Answer

Explanation: As B is undecidable and it can be reduced to C, C is also an undecidable problem.

11. Which of the following options are correct with reference to P-complete problems?

a) used for the problems which are difficult to solve in limited space

b) every problem in P can be reduced to it using proper reductions

c) complete problem for complexity class P

d) all of the mentioned

### View Answer

Explanation:

The notion of P-complete decision problems is useful in the analysis of:

a) which problems are tough to parallelize effectively

b) which problems are difficult to solve in limited space

12. Travelling sales man problem belongs to which of the class?

a) P

b) NP

c) Linear

d) None of the mentioned

### View Answer

Explanation: Travelling Salesman Problem: Given an input matrix of distances between n cities, this problem is to determine if there is a route visiting all cities with total distance less than k.

a) Exact Cover

b) Max Cut

c) 0-1 integer programming

d) None of the mentioned

### View Answer

Explanation: Exact cover is a decision problem in computer science to determine if an exact cover exists.

a) Union

b) Concatenation

c) Kleene

d) All of the mentioned

### View Answer

Explanation: The closure property of PSPACE class includes :- Union, Concatenation and Kleene operation.

a) Quicksort

b) Min Cut

c) Verifying Matrix Multiplication

d) All of the mentioned

### View Answer

Explanation: Freivalds algorithm is a probabalistic randomized algorithm we use to verify matrix multiplication. On the other hand, Randomness can be useful in quicksort. If the algorithm selects pivot element uniformaly at random, it has a probably high probabilty of finishing the work in O(nlogn) time regardless of the input.