gs gs101 Undecidability - The Diagonalization Languages - 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: Which of the following technique is used to find whether a natural language isn’t recursive enumerable?
Diagonalization
Recursive Induction
All of the mentioned
None of the mentioned
Question 2: Diagonalization can be useful in:
To find a non recursively enumerable language.
To prove undecidability of halting problem.
To find a non recursively enumerable language & also proves undecidability of haltig problem
None of the mentioned
Question 3: Which of the following are undecidable problems?
Determining whether two grammars generate the same language
Determining whether a grammar is ambiguous
Determining whether a grammar is ambiguous and two grammars generate the same language
None of the mentioned
Question 4: Which of the following are incorrect options?
Informally, problem is a yes/no question about an infinite set of possible instances
Formally, a problem is a language
All of the mentioned
None of the mentioned
Question 5: If a problem has an algorithm to answer it, we call it _________
decidable
solved
recognizable
none of the mentioned
Question 6: Which of the following are decidable problems?
Can a particular line of code in a program ever be executed?
Do two given CFG’s generate the same language
Is a given CFG ambiguous?
None of the mentioned
Question 7: Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}
A={(M,w)|M is a turing machine that accepts string w}
A concrete undecidable problem
A is recognizable but not decidable
-A is not recognizable
All of the mentioned
Question 8: Which of the following are correct statements?
TMs that always halt are known as Decidable problems
TMs are not guaranteed to halt only on acceptance are recursive enumerable
All of the mentioned
None of the mentioned
Question 9: Statement: If L id R.E., Lc needs to be R.E. Is it correct?
Yes
No
Maybe
Cannot predict
Question 10: Which of the following is true for The Halting problem?
It is recursively enumerable
It is undecidable
It is recursively enumerable and undecidable
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
