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

Question

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

(неупорядоченное чередование-- также иногда называемый «неупорядоченным выбором» --- таков, что L (S | T) = L (S) + L (T), в то время как упорядоченное чередование таково, что L (S | T) = L (S) +(L (T) - {a в L (T): a расширяет некоторый b в L (S)}). Конкретно, шаблон a|aa будет соответствовать строкам a и aa, если чередование неупорядочено,но только a, если чередование упорядочено.)

Другими словами, если шаблон S содержит упорядоченное чередование, можно ли переписать этот шаблон в эквивалентный шаблон T, который не содержит упорядоченных чередований (но, возможно, неупорядоченныхвместо чередования)?

Если бы этот вопрос был рассмотрен в литературе, я был бы признателен за любые ссылки, которые кто-либо может предоставить.Мне почти не удалось развернуть теоретическую работу о выразительной силе расширенных формализмов регулярных выражений (помимо обычных вещей о том, как обратные ссылки переводят вас из обычных языков в неконтекстные грамматики).

Answer 1

in http://swtch.com/~rsc/regexp/regexp3.html [раздел «Соответствует ли регулярное выражение подстроке строки? Если да, то где?»] Необходимо ввести идею приоритетов в «DFA» (вам нужно прочитать все Подозреваю, что серии, чтобы понять, но "DFA" в вопросе расширен от графика NFA "на лету") для обработки упорядоченных чередований. хотя это только обращение к авторитету, а не доказательство, я думаю, что будет справедливо сказать, что если рус Кокс не может этого сделать (выражать заказанные чередования как чистый DFA), то никто не знает, как это сделать.

Answer 2

Я не проверял никакой литературы, но я думаю, что вы можете сконструировать DFA для упорядоченного чередования и тем самым доказать, что он не добавляет выразительной силы следующим образом:

1. Скажем таку нас есть регулярное выражение x || y , где x и y являются регулярными выражениями, а || означает неупорядоченное чередование.Если это так, мы можем построить DFA, принимающие x и y .Мы отметим эти DFA_x и DFA_y
2. Мы построим DFA для x || y в фазах, соединив DFA_x и DFA_y
3. Для каждого пути в DFA_x , соответствующего некоторой строке a (под путем я подразумеваю путь в смысле графа безОбход и ребро дважды, поэтому a - это путь в DFA_ "a *" , но aa - нет) ...
   • Для каждого символав алфавите s
     • Если DFA_y потребляет как (то есть, если запустить как DFA_y , не остановится раньшено это может не обязательно принимать), а DFA_x нет и DFA_x не принимает префикс , так как создает переход из состояния DFA_x заканчивается после потребления a до состояния DFA_y заканчивается после потребления как
4. Принимающие состояния окончательного DFA - все принимающиеТаты обоих входных DFA.Начальное состояние - это начальное состояние DFA_x .

Интуитивно понятно, что это создает две области в выходном DFA.Один из них соответствует первому аргументу чередования, а другой - второму.Пока возможно, что первый аргумент чередования будет совпадать, мы останемся в первой части.Когда встречается символ, который гарантирует, что первый аргумент не будет совпадать, мы переключаемся на вторую часть, если это возможно, на этом этапе.Пожалуйста, прокомментируйте, если этот подход неправильный.