NFAs do not do backtracking. So the solution space would look different. More sane, and more performant, but it would not be a pure regex solution.