Regex (a?)* Не экспоненциально?

Question

В настоящее время я смотрю на проблему регулярных выражений, которые могут в конечном итоге работать в экспоненциальном времени при сопоставлении с определенным входом, например оба (a*)* а также (a|a)* потенциально может иметь " катастрофическое возвращение" при сопоставлении со строкой aaaaab - для каждого дополнительного "a" в сопоставляемой строке время, необходимое для попытки сопоставления строки, удваивается. Это только в том случае, если движок использует подход обратного отслеживания /NFA, пытаясь попробовать все возможные ветви в дереве перед сбоем, например, используемый в PCRE.

Мой вопрос, почему нет (a?)* уязвимы? Исходя из моего понимания обратного отслеживания, то, что должно произойти в строке "aaaab", по сути, происходит с (a|a)*, Если мы создадим NFA, используя стандартную конструкцию Thomspson NFA, конечно, для каждого происходящего эпсилон-перехода двигатель должен будет продолжать принимать их и возвращать их так же, как в случае двух а? Например (пропуская некоторые шаги и где @ заменяет epsilon):

"aaaa" соответствует, но не может соответствовать "b", потерпеть неудачу (возврат)
"aaaa @" соответствует, "b" не выполнено (возврат)
"aaa @ a" соответствует, "b" терпит неудачу (возврат)
"aaa @ a @" соответствует, "b" терпит неудачу (возврат)
...
"@ a @ a @ a @ a @" соответствует, "b" не удается (возврат)

пробуете все возможные комбинации эпсилонов и, конечно, приводящие к экспоненциальному взрыву маршрутов?

Было бы целесообразно удалить эпсилон-переходы из NFA, но я считаю, что это приводит к удалению всего недетерминизма из (a*)* шаблон. Это определенно уязвимо, так что я не совсем уверен, что происходит!

Заранее большое спасибо!

Редактировать: Qtax указал, что epsilons все еще не может присутствовать, когда NFA пересекается с традиционным возвратом, в противном случае (@)* будет пытаться соответствовать навсегда. Так что реализация NFA может привести к (a*)* а также (a|a)* быть экспоненциальным, и (a?)* не так ли? Это суть вопроса на самом деле.

Answer 1

Хорошо, после некоторой проверки мне в конечном итоге удалось выяснить, что это связано с использованием "барьеров" в реализациях NFA. Проще говоря, барьеры размещаются в стратегических точках NFA (например, на узле сразу после перехода "а" в конструкции NFA a*). Они требуют, чтобы матч продолжался с предыдущего раза, когда был достигнут барьер. Это препятствует тому, чтобы NFA когда-либо попадал в ситуацию, когда он соответствует бесконечному количеству эпсилонов, и позволяет ему завершаться.

Другими словами, невозможно перейти от одного барьера к одному и тому же барьеру только в соответствии с электронными движениями - если это произошло, маршрут отбрасывается, и от предыдущей точки происходит возврат. Это также имеет побочный эффект, что (a?)* Не подвержен экспоненциальному взрыву, так как a? не может соответствовать нулю во второй раз.