MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 7 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. |
If n is the length of Input string and m is the number of nodes, the running time of DFA is x that of NFA.Find x? |
| A. | 1/m<sup>2</sup> |
| B. | 2<sup>m</sup> |
| C. | 1/m |
| D. | log m |
| Answer» B. 2<sup>m</sup> | |
| 2. |
The construction time for DFA from an equivalent NFA (m number of node)is: |
| A. | O(m<sup>2</sup>) |
| B. | O(2<sup>m</sup>) |
| C. | O(m) |
| D. | O(log m) |
| Answer» C. O(m) | |
| 3. |
Given Language L= {x {a, b}*|x contains aba as its substring}Find the difference of transitions made in constructing a DFA and an equivalent NFA? |
| A. | 2 |
| B. | 3 |
| C. | 4 |
| D. | Cannot be determined |
| Answer» B. 3 | |
| 4. |
Which of the following is correct proposition?Statement 1: Non determinism is a generalization of Determinism. |
| A. | nStatement 2: Every DFA is automatically an NFA |
| B. | Statement 1 is correct because Statement 2 is correct |
| C. | Statement 2 is correct because Statement 2 is correct |
| D. | Statement 2 is false and Statement 1 is false |
| E. | Statement 1 is false because Statement 2 is false |
| Answer» C. Statement 2 is correct because Statement 2 is correct | |
| 5. |
NFA, in its name has non-deterministic because of : |
| A. | The result is undetermined |
| B. | The choice of path is non-deterministic |
| C. | The state to be transited next is non-deterministic |
| D. | All of the mentioned |
| Answer» C. The state to be transited next is non-deterministic | |
| 6. |
Given Language: L= {ab U aba}*If X is the minimum number of states for a DFA and Y is the number of states to construct the NFA, |
| A. | n|X-Y|=? |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| E. | 1 |
| Answer» B. 2 | |
| 7. |
Which of the following options is correct?Statement 1: Initial State of NFA is Initial State of DFA. |
| A. | nStatement 2: The final state of DFA will be every combination of final state of NFA. |
| B. | Statement 1 is true and Statement 2 is true |
| C. | Statement 1 is true and Statement 2 is false |
| D. | Statement 1 can be true and Statement 2 is true |
| E. | Statement 1 is false and Statement 2 is also false |
| Answer» B. Statement 1 is true and Statement 2 is true | |