Question

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^2

(b) 2^m

(c) 1/m

(d) log m

This question was posed to me by my school teacher while I was bunking the class.

I need to ask this question from Non Deterministic Finite Automata in division Finite Automata of Automata Theory

Answer 1

The correct option is (a) 1/m^2

Explanation: Running time of DFA: O(n) and Running time of NFA =O(m^2n).