Does there exist a "faster" NDFA->DFA algorithm? ================================================ There's no way around the potential exponential running time - it can take you exponential time just to enumerate all of the DFA states. In practice, though, the running time is closer to linear, or sometimes quadratic.