MCQ Computer Science

# 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

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

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.

3. Which of the following contains NP?
a) PSPACE
b) EXPSPACE
c) Both (a) and (b)
d) None of the mentioned

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.
4. An exact cover problem can be represented using:
a) incidence matrix
b) bipartite graph
c) both (a) and (b)
d) none of the mentioned

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.
5. Correct the given order:
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

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

6. NL ? PSPACE ? EXPSPACE
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

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

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) fg=O(hk)
d) None of the mentioned

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

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. Which of the following can be solved in computer science?
a) P=BPP problem
b) NP=co-NP problem
c) Do one way problems exist?
d) All of the mentioned

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

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

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

12. How many DFA’s exits with two states over input alphabet {0,1} ?
a) 16
b) 26
c) 32
d) 64

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

13. Which of the following option is correct?
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

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.

14. The number of tuples in an extended Non Deterministic Finite Automaton:
a) 5
b) 6
c) 7
d) 4

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

15. Which of the following do we use to form an NFA from a regular expression?
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method