## Automata Theory Questions and Answers – Applications of NFA

﻿This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Applications of NFA”. 1. Under which of the following operation, NFA is not closed? a) Negation b) Kleene c) Concatenation d) None of the mentioned 2. It is less complex to prove the closure properties over regular languages using: a) NFA b) … Read more

## Automata Theory Questions and Answers – Class RP and ZPP, Complexity

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 2. The space complexity of a turing machine is undefined if: a) It is a multitape turing machine b) If … Read more

## Automata Theory Questions and Answers – Randomized Algorithm

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Randomized Algorithm” 1. A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits. a) worst case b) best case c) average case d) none of the mentioned 2. Which of … Read more

## Automata Theory Questions and Answers – PSPACE

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “PSPACE”. 1. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space: a) PSPACE b) NPSPACE c) EXPSPACE d) None of the mentioned 2. PSPACE is strictly the super set of: a) Regular … Read more

## Automata Theory Questions and Answers – Node-Cover Problem, Hamilton Circuit Problem

This set of Automata Theory Questions and Answers for Aptitude test focuses on “Node-Cover Problem, Hamilton Circuit Problem”. 1. Which of the given problems are NP-complete? a) Node cover problems b) Directed Hamilton Circuit Problem c) Node cover problems & Directed Hamilton Circuit Problem d) None of the mentioned 2. Which of the following problems … Read more

## Automata Theory Questions and Answers – Non Deterministic Polynomial Time

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Non Deterministic Polynomial Time”. 1. What does NP stands for in complexity classes theory? a) Non polynomial b) Non-deterministic polynomial c) All of the mentioned d) None of the mentioned 2. The hardest of NP problems can be: a) NP-complete b) NP-hard … Read more

## Automata Theory Questions and Answers – Problem Solvable in Polynomial Time

This set of Automata Theory Interview Questions and Answers for Experienced people focuses on “Problem Solvable in Polynomial Time”. 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 … Read more

## Automata Theory Questions and Answers – Rice’s Theorem, Properties and PCP

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Rice’s Theorem, Properties and PCP”. 1. According to the rice’s theorem, If P is a non trivial property, Lp is : a) infinite b) decidable c) undecidable d) none of the mentioned 2. Fill in the blank with reference to Rice’s theorem. … Read more

## Automata Theory Questions and Answers – The Universal Language-Undecidability

This set of Automata Theory Questions and Answers for Experienced people focuses on “The Universal Language-Undecidability”. 1. The decision problem is the function from string to ______________ a) char b) int c) boolean d) none of the mentioned 2. A language L is said to be ____________ if there is a turing machine M such … Read more