MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 15 Mcqs, each offering curated multiple-choice questions to sharpen your Automata Theory knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
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» C. C is decidable if A is reducible to C | |
| 2. |
Can a Modified PCP problem be reduced to PCP? |
| A. | yes |
| B. | no |
| Answer» B. no | |
| 3. |
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» B. false | |
| 4. |
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» E. | |
| 5. |
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 Sb) there exists a TM that recognizes the language not in Sc) both ( |
| A. | there exists a TM that recognizes the language in Sb) there exists a TM that recognizes the language not in Sc) both (a) and ( |
| B. | there exists a TM that recognizes the language not in S |
| C. | both (a) and (b) |
| D. | none of the mentioned |
| Answer» D. none of the mentioned | |
| 6. |
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 functionsb) piecewise functionsc) both ( |
| A. | partial functionsb) piecewise functionsc) both (a) and ( |
| B. | piecewise functions |
| C. | both (a) and (b) |
| D. | none of the mentioned |
| Answer» B. piecewise functions | |
| 7. |
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» D. none of the mentioned | |
| 8. |
CAN_A_MODIFIED_PCP_PROBLEM_BE_REDUCED_TO_PCP??$ |
| A. | yes |
| B. | no |
| Answer» B. no | |
| 9. |
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» C. C is decidable if A is reducible to C | |
| 10. |
PCP stands for? |
| A. | Post Correspondence Problem |
| B. | Post Corresponding Problem |
| C. | Pre Correspondence problem |
| D. | None of the mentioned |
| Answer» B. Post Corresponding Problem | |
| 11. |
Post Correspondence problem is |
| A. | decidable decision problem |
| B. | undecidable decision problem |
| C. | not a decision problem |
| D. | none of the mentioned |
| Answer» C. not a decision problem | |
| 12. |
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» E. | |
| 13. |
Which of the following is incorrect according to rice theorem? |
| A. | |
| B. | there exists a TM that recognizes the language in S |
| C. | there exists a TM that recognizes the language not in S |
| Answer» D. | |
| 14. |
Fill in the blank with reference to Rice’s theorem.$ |
| A. | |
| B. | partial functions |
| C. | piecewise functions |
| Answer» B. partial functions | |
| 15. |
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» D. none of the mentioned | |