# 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

Explanation: 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) all of the mentioned
d) none of the mentioned

Explanation: 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) it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S
d) all of the mentioned

Explanation: 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

Explanation: 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

Explanation: All of the following mentioned are immediate results of Rice’s theorem and thus, undecidable.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Post Correspondence problem is
a) decidable decision problem
b) undecidable decision problem
c) not a decision problem
d) none of the mentioned

Explanation: 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

Explanation: 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

Explanation: PCP or Post Correspondence problem is an undecidable decision problem.

9. Can a Modified PCP problem be reduced to PCP?
a) yes
b) no

Explanation: 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.

Explanation: As B is undecidable and it can be reduced to C, C is also an undecidable problem.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]