Есть ли способ отрицать регулярное выражение?

Учитывая регулярное выражение R, которое описывает регулярный язык (без фантастических обратных ссылок). Существует ли алгоритмический способ построения регулярного выражения R *, описывающего язык всех слов, кроме тех, которые описаны в R? Это должно быть возможно, поскольку Wikipedia говорит:

Регулярные языки закрываются под различными операциями, т.е. если языки K и L регулярны, то есть результат следующих операций: [...] дополнение ¬L

Например, учитывая алфавит {a, b, c}, обратный к языку (abc *) + равен (a | (ac | b | c). *)?

Как уже указывал Деннер в комментариях, инверсия регулярного выражения может быть экспоненциально больше исходного. Это делает обратные регулярные выражения непригодными для реализации синтаксиса отрицательных парциальных выражений для целей поиска. Существует ли алгоритм, который сохраняет характеристику времени выполнения O (n * m) (где n - размер регулярного выражения, а m - длина ввода) регулярного выражения и допускает отрицательные подвыражения?

Ответ 1

К сожалению, ответ, указанный nhahdtdh в комментариях, так же хорош, как мы можем (пока). Определяет ли данное регулярное выражение все строки, является PSPACE-полным. Поскольку все задачи в NP в PSPACE-полные, эффективное решение проблемы универсальности будет означать, что P = NP.

Если бы было эффективное решение вашей проблемы, вы могли бы решить проблему универсальности? Конечно, вы бы.

Используйте эффективный алгоритм для генерации регулярного выражения для отрицания;
Определите, генерирует ли результирующее регулярное выражение пустой набор.

Обратите внимание, что проблема "заданная регулярным выражением, порождает ли она пустое множество" довольно проста:

Регулярное выражение {} генерирует пустой набор.
(r + s) генерирует пустой набор, если оба r и s генерируют пустой набор.
(rs) генерирует пустой набор, если либо r, либо s генерирует пустой набор.
Ничто другое не генерирует пустой набор.

В принципе, довольно легко определить, генерирует ли регулярное выражение пустой набор: просто начните оценивать регулярное выражение.

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

Ответ 2

Wikipedia говорит: ... если существует хотя бы одно регулярное выражение, которое соответствует определенному набору, тогда существует бесконечное число таких выражений. Мы можем вычесть из этого утверждения, что существует бесконечное число выражений, которые описывают язык всех слов, кроме тех, которые описаны в R.

Опять же (как и @nhahtdh пытался объяснить) простейшим алгоритмом для решения этого вопроса является расширение сферы оценки вне контекста самого языка регулярных выражений. То есть: соответствует строкам, которые вы хотите исключить (которые представляют собой конечное подмножество для работы), используя исходное регулярное выражение , а затем обрабатывает любой отказ в соответствии с фактическим соответствием (из бесконечного множества других возможностей). Итак, если результат совпадения отрицательный, ваши строки-кандидаты являются подмножеством действительных решений.