This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Complexity Classes,Class RP and ZPP”.

1. Which among the following is smallest for n=50

a) 2n2

b) n2+3n+7

c) n3

d) 2n

View Answer

Explanation:

2n2=5000

n2+3n+7=2567

n3=125000

2n=1.13*1015

2. The space complexity of a turing machine is undefined if:

a) It is a multitape turing machine

b) If no string of length n causes T to use infinite number of tape squares

c) If some input of length n causes T to loop forever

d) None of the mentioned

View Answer

Explanation: If there exists an input string of length n that causes T to use an infinite number of tape squares, the space complexity of the turing machine is undefined.

3. In order to reduce the run time of a turing machine:

a) we can reduce the number of tapes

b) we can increase the number of tapes

c) use infinite tapes

d) none of the mentioned

View Answer

Explanation: One way to reduce the run time can be to increase the number of tapes. Sometimes, using two tapes can be used to avoid back and forth motions altogether.

4. Which of the following are basic complexity classes for a function f:N->N?

a) Ntime(f)

b) Nspace(f)

c) Space(f)

d) All of the mentioned

View Answer

Explanation: Ntime(f): is a set of languages that can be accepted by a NTM T with non deterministic time complexity function t <=f. In all four cases, the machines are allowed to be multitape TM’s.

5. A function f is called __________ if there exists a TM T so that for any n and any input string of length n, T halts in exactly f(n) moves.

a) Step function

b) Step counting function

c) Inplace functions

d) None of the mentioned

View Answer

Explanation: If f is a step counting function, T is a TM halting in f(n) moves where n is the length of input string.

6. Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)

a) O(nf)

b) O(n+f)

c) O(n^{2}f^{2})

d) None of the mentioned

View Answer

Explanation: Using the encoding function, it is possible to show that if the function f is a step counting function, then the function Cn

^{2}(f(n))

^{2}is the total number of moves required.

7. Which among the following is false?

If f=O(h) and g=O(k) for f,g,h,k:N->N, then

a) f+g = O(h+k)

b) fg = O(hk)

c) f^{g}=O(h^{k})

d) None of the mentioned

View Answer

Explanation: f,g,h,k are partial functions and each is defined at all but a finite number of points.

8. Which of the following is not correct for ZPP?

a) zero error probabalistic polynomial time

b) it runs in non-polynomial time

c) it returns an answer yes, no or do not know

d) none of the mentioned

View Answer

Explanation: ZPP is zero error probabalistic polynomial time complexity class which run in polynomial time, returns an answer: yes, no or do not know.

9. ZPP is based on ________

a) Probabalistic turing machine

b) Alternative turing machine

c) Quantum turing machine

d) None of the mentioned

View Answer

Explanation: A probabalistic turing machine is a non deterministic turing machine which randomly chooses between the available transitions at each point according to some probability distribution.

10. ZPP is exactly equal to the ____________of the classes RP and co-RP.

a) Union

b) Intersection

c) Concatenation

d) Difference

View Answer

Explanation: To prove the following statement, we need to take in note that every problem in RP and co-RP has a Las-Vegas algorithm.

11. Suppose we have a las vegas algorithm C to prove ZPP is contained in RP and co-RP. Run C for double its expected running time.

By Markov’s inequality, the chance that it will answer before we stop is:

a) 1/2

b) 1/4

c) 1/3

d) none of the mentioned

View Answer

Explanation: This means the chance we’ll give the wrong answer on a YES instance, by stopping and yielding NO, is only 1/2, fitting the definition of an RP algorithm.

12. State true or false:

Statement: ZPP is closed under complement function.

a) true

b) false

View Answer

Explanation: ZPP is said to be closed under complement function i.e. ZPP=co-ZPP.

**Sanfoundry Global Education & Learning Series – Automata Theory.**

To practice all areas of Automata Theory, __here is complete set of 1000+ Multiple Choice Questions and Answers__.

**Related Posts:**

- Check Computer Science Books
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Check Automata Theory Books