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.