Почему регулярные выражения могут иметь экспоненциальное время выполнения?

Можно написать регекс, который в некоторых случаях требует экспоненциального времени выполнения. Таким примером является (aa|aa)*. Если на вход подается нечетное количество as, то время выполнения будет экспоненциальным.

Это легко проверить. Если вход содержит только as и имеет длину 51, то регексу потребуется несколько секунд для вычисления (на моей машине). Напротив, если длина входных данных 52, время вычисления не заметно (я проверил это с помощью встроенного Regex-парсера JavaRE).

Я написал Regex-парсер, чтобы найти причину такого поведения, но не нашел ее. Мой парсер может построить AST или NFA на основе Regex. После этого он может перевести NFA в DFA. Для этого используется алгоритм powerset construction algorithm.

Когда я разбираю упомянутый выше Rgex, синтаксический анализатор создает NFA с 7 состояниями - после преобразования в DFA остается только 3 состояния. DFA представляет более разумный Regex (aa)*, который может быть разобран очень быстро.

Таким образом, я не понимаю, почему существуют парсеры, которые могут быть такими медленными. В чем причина этого? Не переводят ли они НФА в ДФА? Если да, то почему? И каковы технические причины, почему они вычисляют так медленно?