gs gs101 Undecidability - Rice's Theorem, Properties and PCP - 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: According to the rice’s theorem, If P is a non trivial property, Lp is :
infinite
decidable
undecidable
none of the mentioned
Question 2: Fill in the blank with reference to Rice’s theorem.
For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.
For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.
partial functions
piecewise functions
all of the mentioned
none of the mentioned
Question 3: Which of the following is incorrect according to rice theorem?
Let S be a set of language hat is non trivial:
Let S be a set of language hat is non trivial:
there exists a TM that recognizes the language in S
there exists a TM that recognizes the language not in S
it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S
all of the mentioned
Question 4: Which of the following set of computable functions are decidable?
The class of computable functions that are constant, and its complement
The class of indices for computable functions that are total
The class of indices for recursively enumerable sets that are cofinite
All of the mentioned
Question 5: Which of the following statements are undecidable?
For a given Turing Machine M,
For a given Turing Machine M,
does M halt on an empty input tape
does M halt for anly inputs at all?
is L(M) regular? Context free? Turing decidable?
all of the mentioned
Question 6: Post Correspondence problem is
decidable decision problem
undecidable decision problem
not a decision problem
none of the mentioned
Question 8: PCP stands for?
Post Correspondence Problem
Post Corresponding Problem
Pre Correspondence problem
None of the mentioned
Question 10: Consider three decision problem A, B, C. A is decidable and B is not. Which of the following is a correct option?
C is undecidable if C is reducible to B
C is undecidable if B is reducible to C
C is decidable if A is reducible to C
C is decidable if C is reducible to B’s complement.
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
