MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 6 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. |
Can a Modified PCP problem be reduced to PCP? |
| A. | yes |
| B. | no |
| Answer» B. no | |
| 2. |
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 | |
| 3. |
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. | |
| 4. |
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 |
| Answer» E. | |
| 5. |
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 |
| Answer» B. piecewise functions | |
| 6. |
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 | |