[thesz]

The problem with DFA is that they explode exponentially for number of choices containing ".*". Then you fail to get a locality of reference, etc. DFA also very sequential.

This is why NDAs are better - you can run several NDAs in parallel with their states and inputs. It basically becomes vectorized problem.

[jeffreyrogers]

Yeah, so it becomes a space/time tradeoff. I think whether which is better depends on the problem you're solving. Many DFAs don't blow up space exponentially, so you'd rather have the DFA in that case. You're right though that for DFAs with an exponential increase in space requirements you are better off just doing the NDA in parallel.