Any NFA that does not have backreferences can be converted to a DFA. If you have backreferences in a regex, you must use an NFA to drive it. Also, backreferen

Any NFA that does not have backreferences can be converted to a DFA. If you have backreferences in a regex, you must use an NFA to drive it. Also, backreferences stand a chance of turning an NFA into NIA. Turns out it's not possible to programmatically determine which backreference-containing regexes will halt or not.