MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 4 Mcqs, each offering curated multiple-choice questions to sharpen your Automata Theory Questions and Answers 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. |
Which of the following statements are undecidable? |
| A. | For a given Turing Machine M, |
| B. | does M halt on an empty input tape |
| C. | does M halt for anly inputs at all? |
| D. | is L(M) regular? Context free? Turing decidable? |
| E. | all of the mentioned |
| Answer» E. all of the mentioned | |
| 3. |
Fill in the blank with reference to Rice’s theorem. |
| A. | For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property. |
| B. | partial functions |
| C. | piecewise functions |
| D. | all of the mentioned |
| E. | none of the mentioned |
| Answer» B. partial functions | |
| 4. |
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 | |