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

1. If the number of steps required to solve a problem is O(nk), then the problem is said to be solved in:

a) non-polynomial time

b) polynomial time

c) infinite time

d) none of the mentioned

### View Answer

Explanation: Most of the operations like addition, subtraction, etc as well as computing functions including powers, square roots and logarithms can be performed in polynomial time. In the given question, n is the complexity of the input and k is some non negative integer.

2. The hardest of NP problems can be:

a) NP-complete

b) NP-hard

c) P

d) None of the mentioned

### View Answer

Explanation: NP class contains many important problems, the hardest of which is NP-complete, whose solution is sufficient to deal with any other NP problem in polynomial time.

a) PSPACE

b) EXPSPACE

c) Both (a) and (b)

d) None of the mentioned

### View Answer

Explanation: It is sufficient to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial time verifier. It is also contained in EXPTIME, since the same algorithm operates in exponential time.

a) incidence matrix

b) bipartite graph

c) both (a) and (b)

d) none of the mentioned

### View Answer

Explanation: The relation ‘contains’ can be represented using a bipartite graph. The vertices of the graph can be divided into two disjoint sets, one representing the subset S and the other representing the elements of P and one edge for each subset in S;each node is included in exactly one of the edges forming the cover.

NL? P? NP? PH? PSPACE

a) NP? P? NL? PH? PSPACE

b) NL? PH? NP? P? PSPACE

c) NL? P? NP? PH? PSPACE

d) None of the mentioned

### View Answer

Explanation: The given order is the only correct order and further PSPACE belongs to EXPTIME class and subsequently occurs EXPSPACE class.

The given relation involves which of the following theorems?

a) Space hierarchy theorem

b) Savitch’s theorem

c) Both (a) and (b)

d) None of the mentioned

### View Answer

Explanation: From space hierarchy theorem: NL ? NPSPACE, from Savitch’s theorem: NPSPACE= PSPACE.

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) fg=O(hk)

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.

a) P=BPP problem

b) NP=co-NP problem

c) Do one way problems exist?

d) All of the mentioned

### View Answer

Explanation: There exists a list of unsolved problems in computational theory which includes many problems including the ones given.

10. Given: ?= {a, b}

L= {x??*|x is a string combination}

?4 represents which among the following?

a) {aa, ab, ba, bb}

b) {aaaa, abab, e, abaa, aabb}

c) {aaa, aab, aba, bbb}

d) All of the mentioned

### View Answer

Answer: b

Explanation: ?* represents any combination of the given set while ?x represents the set of combinations with length x where x ? I.

11. Regular expression for all strings starts with ab and ends with bba is.

a) aba*b*bba

b) ab(ab)*bba

c) ab(a+b)*bba

d) All of the mentioned

### View Answer

Explanation: Starts with ab then any number of a or b and ends with bba.

a) 16

b) 26

c) 32

d) 64

### View Answer

Explanation: Number of DFA’s = 2n * n(2*n).

a) NFA is slower to process and its representation uses more memory than DFA

b) DFA is faster to process and its representation uses less memory than NFA

c) NFA is slower to process and its representation uses less memory than DFA

d) DFA is slower to process and its representation uses less memory than NFA

### View Answer

Explanation: NFA, while computing strings, take parallel paths, make different copies of input and goes along different paths in order to search for the result. This creates the difference in processing speed of DFA and NFA.

a) 5

b) 6

c) 7

d) 4

### View Answer

Explanation: For NFA or extended transition function on NFA, the tuple elements remains same i.e. 5.

a) Subset Construction Method

b) Power Set Construction Method

c) Thompson Construction Method

d) Scott Construction Method

### View Answer

Explanation: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.