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

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

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

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

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


regex algorithm regular-language
person fuz    schedule 11.03.2013    source источник
comment
Создайте NFA из регулярного выражения, создайте DFA из NFA (для этого должен быть алгоритм), превратите нетерминальные состояния в терминальные состояния и наоборот, затем получите регулярное выражение из DFA.   -  person nhahtdh    schedule 11.03.2013
comment
@nhahtdh Звучит как интересная идея; проблема в том, что NFA длины O(n) может соответствовать DFA длины O(2^n).   -  person fuz    schedule 11.03.2013
comment
Я не проводил надлежащего изучения этой темы, но я не понимаю, как NFA может генерировать больший DFA. Можете ли вы показать мне один такой случай?   -  person nhahtdh    schedule 11.03.2013
comment
@nhahtdh Каждое состояние DFA, связанное с NFA, является доступным членом набора мощности NFA. Это дает верхнюю границу 2 ^ n состояний, где n — количество состояний NFA. Этого можно достичь, создав обычный язык, в котором можно достичь каждого подмножества состояний NFA. Где-то был простой пример, но я просто не могу его найти.   -  person fuz    schedule 11.03.2013
comment
См. соответствующий вопрос в теоретическом переполнении стека CS. Регулярное выражение NFA-›DFA-›inversion-› оптимально для наихудшего случая.   -  person thiton    schedule 11.03.2013
comment
Ваша цитата из Википедии не совпадает с вашим описанием проблемы. Реверс языка — это набор всех строк этого языка в обратном порядке. т. е. если L = {ab, abc, aba}, то, наоборот, L^R = {ba, cba, aba}. Несмотря на это, по-прежнему верно, что отрицание (или, говоря более технически, дополнение) по-прежнему является регулярным.   -  person DPenner1    schedule 11.03.2013
comment
@DPenner Прошу прощения. Я, возможно, неправильно прочитал ту статью.   -  person fuz    schedule 11.03.2013
comment
@FUZxxl Все в порядке, формальные языки могут сбивать с толку! Однако, как вы правильно заметили, стандартный алгоритм отрицания регулярного выражения - это O (2 ^ n) в пространстве, и он был бы непрактичным для языков с большим количеством состояний в его NFA.   -  person DPenner1    schedule 11.03.2013
comment
Это, безусловно, интересный вопрос, но действительно ли это вопрос программирования? Не лучше ли это подходит для ComputerScience? (Тем более, что вы, кажется, не заинтересованы в разработке, пусть и не математически чистых, решений?)   -  person JDB still remembers Monica    schedule 11.03.2013
comment
@Cyborgx37 Позвольте мне процитировать часто задаваемые вопросы: Мы считаем, что лучшие вопросы о переполнении стека содержат немного исходного кода, но если ваш вопрос в целом охватывает… • конкретную проблему программирования • программный алгоритм   -  person fuz    schedule 11.03.2013
comment
Все сводится к вопросу программирования. Вы можете делать много забавных вещей с простыми (или действительно регулярными) регулярными выражениями, которые вы не можете делать с расширенными регулярными выражениями, например, позволяя ненадежному пользователю использовать их для поиска, поскольку они имеют гарантированное линейное время выполнения. Все наборы инструментов для простого регулярного выражения, которые я знаю, не поддерживают обратное сопоставление, хотя их можно преобразовать в обычное регулярное выражение. Было бы неплохо узнать, существует ли алгоритм, позволяющий реализовать обратный оператор сопоставления без нарушения линейной временной сложности.   -  person fuz    schedule 11.03.2013
comment
@Cyborgx37 «… программирование связано …». 'достаточно.   -  person Konrad Rudolph    schedule 11.03.2013
comment
@FUZxxl: На практике для вашей второй части обычно требуется проверить, есть ли совпадение, а затем логически отрицать результат или использовать отрицательную упреждающую конструкцию в (ir) регулярном выражении.   -  person nhahtdh    schedule 11.03.2013
comment
@nhahtdh Заглянуть вперед не является частью простого регулярного выражения. Это может нарушить линейную сложность.   -  person fuz    schedule 11.03.2013
comment
@FUZxxl: рассмотрите расширение простого регулярного выражения, где вы можете иметь простое регулярное выражение ИЛИ отрицательное упреждающее утверждение, которое может содержать только обычное регулярное выражение внутри (даже не другое утверждение внутри). Думаю сложность будет такая же. Сложность нарушается только тогда, когда у вас есть дикая смесь простого регулярного выражения и просмотра вперед.   -  person nhahtdh    schedule 11.03.2013
comment
@FUZxxl - Хорошо, я покупаю. Подумайте, однако, что вы не можете доказать отрицательное. В большинстве отраслей науки чаще всего бывает так, что вопрос должен быть сформулирован как положительный, а затем ответ дан в виде доказательств, подтверждающих его (или их отсутствие). Я полагаю, вы обнаружите, что то же самое верно для всех, кроме самых тривиальных регулярных выражений. Гораздо проще выразить то, что вы ищете, чем отрицать результат.   -  person JDB still remembers Monica    schedule 11.03.2013
comment
@Cyborgx37 Cyborgx37 Как писал nhahtdh в самом первом комментарии, действительно легко (в том смысле, что алгоритм прост) можно вычислить обратное регулярному выражению. Это просто непросто (в том смысле, что имеет высокую вычислительную сложность).   -  person fuz    schedule 12.03.2013
comment
@nhahtdh Разве это не требует возврата? Ключом к реализации линейного времени является избегание адского возврата.   -  person fuz    schedule 12.03.2013
comment
Проблема с моим расширением заключается в том, что, хотя полезно отрицать какое-то простое регулярное выражение, оно нарушает свойство, при котором 2 регулярных выражения могут быть свободно объединены, объединены ИЛИ вместе, что, я думаю, является мотивацией для поиска простого регулярного выражения, которое является отрицанием другого простого регулярного выражения.   -  person nhahtdh    schedule 12.03.2013
comment
@FUZxxl: если предположить, что вы можете сопоставить строку с линейной сложностью (или подтвердить отсутствие совпадения) с простым регулярным выражением, отрицательный просмотр вперед просто сведет на нет результат сопоставления. (Если предположение неверно, то даже обычному регулярному выражению будет сложно проверить отсутствие совпадения).   -  person nhahtdh    schedule 12.03.2013
comment
@nhahtdh Я не могу представить, как это должно работать. Не могли бы вы опубликовать более подробный набросок алгоритма в ответе?   -  person fuz    schedule 12.03.2013
comment
@FUZxxl: это не алгоритм или что-то в этом роде. Проще говоря, это форма checking whether there is a match, then logically negate the result (соответствует --› ложь, нет совпадений --› истина).   -  person nhahtdh    schedule 12.03.2013
comment
@nhahtdh Кажется, это не работает, когда выражение с отрицанием является частью большего выражения.   -  person fuz    schedule 12.03.2013
comment
@FUZxxl: Конечно, это не удастся (проверьте мое формальное определение расширения и предостережение несколькими комментариями позже)   -  person nhahtdh    schedule 12.03.2013
comment
Да дополнение обычного языка является обычным и существует Алгоритмическим способом можно написать дополнение регулярного выражения к регулярному выражению. Кроме того, как DPenner говорит о неэффективности. Мы всегда можем хорошо RE в соответствии с минимизированным DFA. Таким образом, для RE мы можем оценить RE, который способен принимать дополнительный язык.   -  person Grijesh Chauhan    schedule 15.03.2013
comment
Что вы имеете в виду: «Мы всегда можем получить хороший RE в соответствии с минимизированным DFA«   -  person fuz    schedule 16.03.2013
comment
@FUZxxl нет! вот почему я использую слово «хороший» вместо «минимизированный».   -  person Grijesh Chauhan    schedule 17.03.2013
comment
@GrjeshChauhan Я до сих пор не понимаю, что ты хочешь мне сказать. Мне жаль. У меня проблемы с разбором вашей грамматики.   -  person fuz    schedule 17.03.2013
comment
@FUZxxl OK, (1) Дополнение обычного языка (RE) является обычным (2) для поиска RE дополнительного языка. делай как RE-->NFA-->DFA-->minimized DFA --> COMPLEMENT DFA --> RE. (a) RE-->NFA является алгоритмическим синтаксическим анализатором LEX (b) NFA --> DFA является алгоритмическим (c) DFA --> MINIMIZED DFA снова алгоритмическим (как b, так и c школьные задания) (d) DFA --> COMPLEMENT DFA является алгоритмическим (прочитав мой ответ Я понял, что вы можете реализовать) (e) дополнение DFA-->RE - это алгоритм, использующий ТЕОРЕМУ АРДЕНА. Итак, что я хочу сказать, для данного RE вы можете найти RE для дополнения.   -  person Grijesh Chauhan    schedule 17.03.2013
comment
@FUZxxl, потому что для дополнительного DFA нам нужно сделать дополнительный DFA (не частичный). Вот почему мы получаем сложный RE для дополнительного языка. Но мы можем выполнить некоторую работу по сокращению, MINIMIZE дополнительно DFA   -  person Grijesh Chauhan    schedule 17.03.2013
comment
@Grjesh Спасибо, что подытожили то, что сказали все остальные. Проблема в том, что размер DFA может быть экспоненциальным по отношению к размеру NFA, в результате чего регулярное выражение дополнения будет иметь экспоненциальный размер по сравнению с исходным регулярным выражением.   -  person fuz    schedule 17.03.2013
comment
@FUZxxl Да, но вы всегда можете свернуть NFA в DFA. Также то, что я имею в виду, полный DFA всегда имеет больше состояний.   -  person Grijesh Chauhan    schedule 17.03.2013
comment
@GrjeshChauhan Скажите, пожалуйста, как это уменьшает длину сгенерированного регулярного выражения или промежуточного DFA.   -  person fuz    schedule 17.03.2013

Ответы (2)


arrow_upward
4
arrow_downward

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

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

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

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

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

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

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

person Patrick87    schedule 11.03.2013
comment
Whether a given regular expression generates all strings - Здесь описание проблемы весьма расплывчато. Я не знаю, о чем ты говоришь. - person nhahtdh; 11.03.2013
comment
Спасибо за ответ. Не могли бы вы, если хотите, исследовать и вторую часть моего вопроса? - person fuz; 11.03.2013
comment
Является ли данное регулярное выражение генерирующим все строки PSPACE-полным. Я ищу доказательство этого утверждения, у вас есть? - person a3nm; 01.06.2019

arrow_upward
1
arrow_downward

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

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

person Alex Filipovici    schedule 11.03.2013
comment
then compare it with the finite set of candidates you provide Не совсем так. Просто попробуйте сопоставить строку с (простым) регулярным выражением. Если не совпадает = совпадение. Это работает только в том случае, если вы хотите особенно свести на нет целое обычное регулярное выражение. Он не может конкатенировать. - person nhahtdh; 12.03.2013
comment
@nhahtdh, я попытался переформулировать ответ. Во всяком случае, я не вижу реального применения вопроса. - person Alex Filipovici; 12.03.2013
comment
Проверьте этот комментарий - person nhahtdh; 12.03.2013