Automata Theory Multiple Choice Questions 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
Answer: c
Clarification: Rice’s theorem states that ‘Any non trivial property about the language recognized by a turing machine is undecidable’.
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.
a) partial functions
b) piecewise functions
c) both (a) and (b)
d) none of the mentioned
Answer: a
Clarification: A property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm.
3. Which of the following is incorrect according to rice theorem?
Let S be a set of language hat is non trivial:
a) there exists a TM that recognizes the language in S
b) there exists a TM that recognizes the language not in S
c) both (a) and (b)
d) none of the mentioned
Answer: c
Clarification: According to rice theorem, it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S.
4. Which of the following set of computable functions are decidable?
a) The class of computable functions that are constant, and its complement
b) The class of indices for computable functions that are total
c) The class of indices for recursively enumerable sets that are cofinite
d) All of the mentioned
Answer: d
Clarification: According to Rice’s theorem, if there exists atleast one computable function in a particular class C of computable functions and another computable function not in C then the problem deciding whether a particular program computes a function in C is undecidable.
5. Which of the following statements are undecidable?
For a given Turing Machine M,
a) does M halt on an empty input tape
b) does M halt for anly inputs at all?
c) is L(M) regular? Context free? Turing decidable?
d) all of the mentioned
Answer: d
Clarification: All of the following mentioned are immediate results of Rice’s theorem and thus, undecidable.
6. Post Correspondence problem is
a) decidable decision problem
b) undecidable decision problem
c) not a decision problem
d) none of the mentioned
Answer: b
Clarification: Post Correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Being simpler than halting problem, it can be used in proofs of undecidability.
7. State true or false:
Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.
a) true
b) false
Answer: a
Clarification: The MPCP is : Given lists A and B of K strings ,say A = w1 ,w2, …wk and B= x1, x2,…..xk does there exists a sequence of integers i1,i2,…ir such that w1wi1wi2…..wir = x1xi1xi2…xir?
8. PCP stands for?
a) Post Correspondence Problem
b) Post Corresponding Problem
c) Pre Correspondence problem
d) None of the mentioned
Answer: a
Clarification: PCP or Post Correspondence problem is an undecidable decision problem.
9. Can a Modified PCP problem be reduced to PCP?
a) yes
b) no
Answer: a
Clarification: Yes, it can be. There exists a theorem and as well as its proof which supports the assertion.
10. Consider three decision problem A, B, C. A is decidable and B is not. Which of the following is a correct option?
a) C is undecidable if C is reducible to B
b) C is undecidable if B is reducible to C
c) C is decidable if A is reducible to C
d) C is decidable if C is reducible to B’s complement.
Answer: b
Clarification: As B is undecidable and it can be reduced to C, C is also an undecidable problem.