Explore topic-wise MCQs in Automata Theory.

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>
Discussion
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)
Discussion
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
Discussion
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
Discussion
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
Discussion
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
Discussion
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
Discussion