Automata Theory MCQ

Test your knowledge with important Automata Theory MCQ and their applications. These MCQs are beneficial for competitive exams too. Explore 30 + more Automata Theory MCQs at Bissoy

• State true or false: Statement: ZPP is closed under complement function.
  ক

  true

  খ

  false
• 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:
  ক

  1/2

  খ

  1/4

  গ

  1/3

  ঘ

  none of the mentioned
• ZPP is exactly equal to the ____________of the classes RP and co-RP.
  ক

  Union

  খ

  Intersection

  গ

  Concatenation

  ঘ

  Difference
• ZPP is based on ________
  ক

  Probabalistic turing machine

  খ

  Alternative turing machine

  গ

  Quantum turing machine

  ঘ

  None of the mentioned
• Which of the following is not correct for ZPP?
  ক

  zero error probabalistic polynomial time

  খ

  it runs in non-polynomial time

  গ

  it returns an answer yes, no or do not know

  ঘ

  none of the mentioned
• Which among the following is false? If f=O(h) and g=O(k) for f,g,h,k:N->N, then
  ক

  f+g = O(h+k)

  খ

  fg = O(hk)

  গ

  fg=O(hk)

  ঘ

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

  O(nf)

  খ

  O(n+f)

  গ

  O(n2f2)

  ঘ

  None of the mentioned
• 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.
  ক

  Step function

  খ

  Step counting function

  গ

  Inplace functions

  ঘ

  None of the mentioned
• Which of the following are basic complexity classes for a function f:N->N?
  ক

  Ntime(f)

  খ

  Nspace(f)

  গ

  Space(f)

  ঘ

  All of the mentioned
• In order to reduce the run time of a turing machine:
  ক

  we can reduce the number of tapes

  খ

  we can increase the number of tapes

  গ

  use infinite tapes

  ঘ

  none of the mentioned
• The space complexity of a turing machine is undefined if:
  ক

  It is a multitape turing machine

  খ

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

  গ

  If some input of length n causes T to loop forever

  ঘ

  None of the mentioned
• Which among the following is smallest for n=50
  ক

  2n2

  খ

  n2+3n+7

  গ

  n3

  ঘ

  2n
• Which of the following can be referred to as applications of Randomized algorithm?
  ক

  Quicksort

  খ

  Min Cut

  গ

  Verifying Matrix Multiplication

  ঘ

  All of the mentioned
• Which of the following can be solved in computer science?
  ক

  P=BPP problem

  খ

  NP=co-NP problem

  গ

  Do one way problems exist?

  ঘ

  All of the mentioned
• State true or false: Statement: A turing machine has the capability of using randomly ‘generated’ numbers.
  ক

  true

  খ

  false
• Unix sort command uses _________ as its sorting technique.
  ক

  Quick Sort

  খ

  Bucket Sort

  গ

  Radix Sort

  ঘ

  Merge Sort
• Prisonner’s dilemma can be related to the following:
  ক

  cooperative behaviour

  খ

  graph theory

  গ

  all of the mentioned

  ঘ

  None of the mentioned
• Which of the following algorithms are probably correct as well as fast?
  ক

  Las Vegas Algorithm

  খ

  Monte Carlo Algorithm

  গ

  Atlantic City Algorithm

  ঘ

  All of the mentioned
• Which of the following are probalistic algorithms?
  ক

  Las Vegas Algorithm

  খ

  Monte Carlo Algorithm

  গ

  Atlantic City Algorithm

  ঘ

  All of the mentioned
• Which of the following options match the given statement: Statement: The algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time.
  ক

  Las Vegas Algorithm

  খ

  Monte Carlo Algorithm

  গ

  Atlantic City Algorithm

  ঘ

  None of the mentioned
• A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.
  ক

  worst case

  খ

  best case

  গ

  average case

  ঘ

  none of the mentioned
• Which of the following PSPACE can be characterized into?
  ক

  APTIME

  খ

  AP

  গ

  Quantom complexity class

  ঘ

  None of the mentioned
• Complement of all the problems in PSPACE is ________
  ক

  PSPACE

  খ

  NL

  গ

  P

  ঘ

  All of the mentioned
• Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.
  ক

  time

  খ

  space

  গ

  both time and space

  ঘ

  none of the mentioned
• Statement : All PSPACE problems can be reduced to PSPACE-complete problems. State true or false:
  ক

  true

  খ

  false
• NL ∈ PSPACE ∈ EXPSPACE The given relation involves which of the following theorems?
  ক

  Space hierarchy theorem

  খ

  Savitch’s theorem

  গ

  Space hierarchy and Savitch’s theorems

  ঘ

  None of the mentioned
• Correct the given order: NL∈ P∈ NP∈ PH∈ PSPACE
  ক

  NP∈ P∈ NL∈ PH∈ PSPACE

  খ

  NL∈ PH∈ NP∈ P∈ PSPACE

  গ

  NL∈ P∈ NP∈ PH∈ PSPACE

  ঘ

  None of the mentioned
• The class PSPACE is closed under the following operations:
  ক

  Union

  খ

  Concatenation

  গ

  Kleene

  ঘ

  All of the mentioned
• Savitch theorem relates to which of the following:
  ক

  PSPACE=NPSPACE

  খ

  Alternating Turing Machine

  গ

  Time complexity

  ঘ

  None of the mentioned
• PSPACE is strictly the super set of:
  ক

  Regular language

  খ

  Context free language

  গ

  Context Sensitive Language

  ঘ

  None of the mentioned