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

advertisement

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

advertisement

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

advertisement

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

advertisement

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

advertisement

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

advertisement

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

advertisement

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

advertisement

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

advertisement

Automata Theory Questions and Answers – The Diagonalization Languages

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The Diagonalization Languages” 1. Which of the following technique is used to find whether a natural language isn’t recursive enumerable? a) Diagonalization b) Recursive Induction c) All of the mentioned d) None of the mentioned 2. Diagonalization can be useful in: a) … Read more

advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.