I think you've pretty much nailed the main tradeoffs on the head. NFAs can be more memory efficient because they can encode O(2n) different configurations in O(n) space, whereas a DFA for the same language might take exponential space. You're similarly correct that NFAs have slower updates; most algorithms for simulating NFAs take O(n) time to compute state transitions (where n is the number of states) vs O(1) time for DFAs.
There are a few other differences between the two. For starters, DFAs are usually easier to encode, since for each pair of state and symbol there's exactly one transition. This lends itself naturally to a multidimensional array for a transition table. By contrast, an NFA (or worse, an ε-NFA) usually requires a more complex representation because there can be a large number of transitions for any state. However, NFAs do have the advantage that many transformations from complex structures to automata are simpler with NFAs. For example, the canonical construction of a matching automaton from a regular expression generates an ε-NFA rather than a DFA, since the transformation is best expressed by recursively building up smaller ε-NFAs and then joining them together using ε-moves. It's possible to directly convert the regular expression to a DFA, but it's considerably more difficult to do so. Similarly, many algorithms for generating LR(k) parsers can be more intuitively motivated by exploring how the handle recognition automaton works in terms of NFAs rather in terms of DFAs (though most algorithms for generating these parsers go directly to the DFA rather than the NFA).
Hope this helps!
0
Foo Bah
On
NFA representations are more compact, but DFA's are easier to simulate. Oftentimes there is an exponential size increase when an NFA is reduced to a DFA
I think you've pretty much nailed the main tradeoffs on the head. NFAs can be more memory efficient because they can encode O(2n) different configurations in O(n) space, whereas a DFA for the same language might take exponential space. You're similarly correct that NFAs have slower updates; most algorithms for simulating NFAs take O(n) time to compute state transitions (where n is the number of states) vs O(1) time for DFAs.
There are a few other differences between the two. For starters, DFAs are usually easier to encode, since for each pair of state and symbol there's exactly one transition. This lends itself naturally to a multidimensional array for a transition table. By contrast, an NFA (or worse, an ε-NFA) usually requires a more complex representation because there can be a large number of transitions for any state. However, NFAs do have the advantage that many transformations from complex structures to automata are simpler with NFAs. For example, the canonical construction of a matching automaton from a regular expression generates an ε-NFA rather than a DFA, since the transformation is best expressed by recursively building up smaller ε-NFAs and then joining them together using ε-moves. It's possible to directly convert the regular expression to a DFA, but it's considerably more difficult to do so. Similarly, many algorithms for generating LR(k) parsers can be more intuitively motivated by exploring how the handle recognition automaton works in terms of NFAs rather in terms of DFAs (though most algorithms for generating these parsers go directly to the DFA rather than the NFA).
Hope this helps!