gs gs101 Undecidability - The Universal Language-Undecidability - Quiz No.1
gs gs101 Automata Theory Quiz
This quiz belongs to book/course code gs gs101 Automata Theory of gs organization. We have 92 quizzes available related to the book/course Automata Theory. This quiz has a total of 10 multiple choice questions (MCQs) to prepare and belongs to topic Undecidability. NVAEducation wants its users to help them learn in an easy way. For that purpose, you are free to prepare online MCQs and quizzes.
NVAEducation also facilitates users to contribute in online competitions with other students to make a challenging situation to learn in a creative way. You can create one to one, and group competition on an topic of a book/course code. Also on NVAEducation you can get certifications by passing the online quiz test.
Question 1: The decision problem is the function from string to ______________
char
int
boolean
none of the mentioned
Question 2: A language L is said to be ____________ if there is a turing machine M such that L(M)=L and M halts at every point.
Turing acceptable
decidable
undecidable
none of the mentioned
Question 3: Which among the following are undecidable theories?
The first order theory of boolean algebra
The first order theory of Euclidean geomentry
The first order theory of hyperbolic geometry
The first order theory of the natural number with addition, multiplication, and equality
Question 4: Rec-DFA = { | M is a DFA and M recognizes input w}.
Fill in the blank:
Rec-DFA is ___________
Fill in the blank:
Rec-DFA is ___________
Undecidable
Decidable
Non finite
None of the mentioned
Question 5: Which among the following are semi decidable?
Empty-DFA
Rec-NFA
Infinite-DFA
All of the mentioned
Question 6: The language accepted by a turing machine is called ____________
Recursive Ennumerable
Recursive
Recursive Ennumerable and Recursive
None of the mentioned
Question 7: Decidable can be taken as a synonym to:
recursive
non recursive
recognizable
none of the mentioned
Question 8: The problems which have no algorithm, regardless of whether or not they are accepted by a turing machine that fails to halts on some input are referred as:
Those that have an algorithm
Intractable problems: Those that are only solved by a turing machine that may run forever on inputs they do not accept.
Computable
None of the mentioned
Question 9: An algorithm is called efficient if it runs in ____________ time on a serial computer.
polynomial
non polynomial
logarithmic
none of the mentioned
Question 10: A problem is called __________ if its has an efficient algorithm for itself.
tractable
intractable
computational
none of the mentioned
Online Quizzes of gs101 Automata Theory
Other Classes Of Problems - Randomized Algorithm - Quiz No.1
gs gs101
Automata Theory Online Quizzes
Push Down Automata - DPDA and Ambiguous Grammars - Quiz No.1
gs gs101
Automata Theory Online Quizzes
