FWIW the equivalence between NFA and DFA requires an exponential space increase to encode the NFA as a DFA, with an exponential space blow up you can encode a lot of things as DFAs (I'm pretty sure you could encode a Turing machine that uses bounded space on the tape as a DFA with exponentially more space, "just" make each possible configuration one state in the DFA)