Search code examples
compiler-constructiontimetime-complexitydfanfa

time complexity trade offs of nfa vs dfa

I am looking for a discussion on which is better used and in what circumstances in a compiler an nfa or dfa. what are the time complexity trade-offs of simulating an nfa vs dfa and which one is more suitable during what circumstances in a compiler??

Solution
    • The construction time for a DFA from an NFA is O(2^m) where m is the number of nodes.
    • The running time of a DFA is O(n) where n is the length of the input string. This is because there is only 1 path through the DFA for a given string.
    • The construction time for an NFA should be O(m), where m is the number of nodes
    • The running time for an NFA is O(m²n) because it is non-deterministic and the computer must check every possible path for the current character in the string. (assuming no lookahead, it doesn't know what the next character will be so it runs into dead ends)

    These figures might give u a brief idea