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
View Answer

Answer: c
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
View Answer

Answer: a
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
View Answer

Answer: d
Explanation: According to rice theorem, it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S.
advertisement
advertisement

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
View Answer

Answer: d
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
View Answer

Answer: d
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
View Answer

Answer: b
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
View Answer

Answer: a
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?
advertisement

8. PCP stands for?
a) Post Correspondence Problem
b) Post Corresponding Problem
c) Pre Correspondence problem
d) None of the mentioned
View Answer

Answer: a
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
View Answer

Answer: a
Explanation: Yes, it can be. There exists a theorem and as well as its proof which supports the assertion.
advertisement

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.
View Answer

Answer: b
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]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.