Как определить, является ли regex ортогональным к другому regex?

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

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

С другой стороны, я - теоретик...

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

Каждое регулярное выражение определяет регулярный язык всех строк, которые могут быть сгенерированы выражением, или если Вы предпочитаете всех строк, которые "подобраны" регулярным выражением. Думайте о языке как о ряде строк. В большинстве случаев набор будет бесконечно большим. Ваш вопрос спрашивает, пусты ли пересечения двух множеств, данных регулярными выражениями, или нет.

По крайней мере в первом приближении, я не могу вообразить способ ответить на тот вопрос, не вычисляя наборы, которые для бесконечных множеств займут больше времени, чем Вы имеете. Я думаю, что мог бы быть способ вычислить ограниченный набор и определить, когда шаблон разрабатывается вне того, что требуется другим regex, но это не было бы просто.

, Например, просто рассмотрите простые выражения (ab)* и (aba)*b. Каков алгоритм, который решит генерировать abab от первого выражения и затем остановиться, не проверяя ababab, abababab, и т.д. потому что они никогда не будут работать? Вы не можете только генерировать строки и проверку, пока соответствие не найдено, потому что это никогда не завершалось бы, когда языки являются непересекающимися. Я не могу вообразить ничего, что работало бы в общем случае, но затем существуют люди намного лучше, чем я в такого рода вещи.

, В целом, это - тяжелая проблема. Я был бы немного удивлен узнать, что существует полиномиально-разовое решение, и я не был бы вообще удивлен узнать, что это эквивалентно проблеме остановки. Хотя, учитывая, что регулярные выражения не полны по Тьюрингу, кажется, по крайней мере, возможным, что решение существует.

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

, Который походит на стреляющих воробьев с орудием. Почему не только создают автомат продукта и проверку, если принять состояние достижимо от начального состояния? Это также даст Вам строку в пересечении немедленно, не имея необходимость создавать регулярное выражение сначала.

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

я только знаю о способе сделать это, который включает создание DFA от regexp, который является экспоненциальным временем (в вырожденном случае). Это приводимо к проблеме остановки, потому что все, но проблема остановки не приводима к это .

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

Так, учитывая то, что я думаю, что Вы используете в качестве определения для ортогонального, если Вы переводите свой REs в FSMs и те FSMs, не равны, REs являются ортогональными.

Это не корректно. У Вас может быть два DFAs (FSMs), которые неизоморфны в маркированном краем смысле мультиграфа, но принимают те же языки. Кроме того, были то, что не случай, Ваш тест проверит, приняли ли два regexps не - идентичный , тогда как OP хочет не - наложение языки (пустое пересечение).

кроме того, знать, что \1, \2..., \9 конструкций не являются регулярными: этого нельзя выразить с точки зрения конкатенации, объединения и * (звезда Kleene). Если Вы хотите включать назад замену, я не знаю, каков ответ. Также интереса то, что соответствующая проблема для контекстно-свободных языков неразрешима: нет никакого алгоритма, который берет две контекстно-свободных грамматики G1 и G2 и возвращает истинную эквивалентность L (G1) в€ © L (g2) в ‰ Г ˜.

fsmtools может сделать все виды операций на конечных автоматах, Ваша единственная проблема состояла бы в том, чтобы преобразовать строковое представление регулярного выражения в формат, с которым может работать fsmtools. Это определенно возможно для простых случаев, но будет хитро в присутствии расширенных функций как взгляд {вперед, позади}.

Вы могли бы также взглянуть на OpenFst, хотя я никогда не использовал его. Это поддерживает пересечение, все же.

Точное замечание об этих \1, \2 бита... это - свободный контекст, и таким образом, не разрешимый. Деталь: Не ВСЕ приводимо для Остановки... Эквивалентность программы, например.. †“Brian Postow

[я отвечаю на комментарий]

, IIRC, a^n b^m a^n b^m не является свободным контекстом, и таким образом (a\*)(b\*)\1\2 не ни один, так как это - то же. ISTR { ww | w ∈ L }, не являющийся "хорошим", даже если L "хорош", для хорошего, являющегося одним из regular, context-free.

я изменяю свой оператор: все в РЕ приводимо к проблеме остановки ;-)

Можно, возможно, использовать что-то как Regexp:: Genex для генерации тестовых строк, чтобы соответствовать указанному regex и затем использовать тестовую строку на 2-м regex, чтобы определить, являются ли 2 regexes ортогональными.

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

Я верю , kdgregory корректен, Вы используете Ортогональный для значения Дополнение .

, это исправляет?

Я говорил слишком скоро. То, что я сказал в своем исходном сообщении, не удастся, но существует процедура того, что Вы пытаетесь сделать, если можно преобразовать регулярные выражения в форму DFA.

можно найти процедуру в книге, которую я упомянул в своем первом сообщении: "Введение в Теорию Вычисления" 2-й выпуск Sipser. Это находится на странице 46 с деталями в сноске.

процедура дала бы Вам новый DFA, который является пересечением двух DFAs. Если новый DFA имел достижимое, принимают состояние затем, пересечение непусто.

Преобразуйте каждое регулярное выражение в DFA. От принять состояния одного DFA создают переход эпсилона к начальному состоянию второго DFA. Вы в действительности создадите NFA путем добавления перехода эпсилона. Затем преобразуйте NFA в DFA. Если начальное состояние не является принять состоянием, и принять состояние достижимо, то эти два регулярных выражения не являются "ортогональными". (Так как их пересечение непусто.)

существуют, знают процедуры преобразования регулярного выражения к DFA и преобразования NFA к DFA. Вы могли посмотреть на книгу как "Введение в Теорию Вычисления" Sipser для процедур или просто искать вокруг сети. Несомненно многие старшекурсники и выпускники должны были сделать это для одного класса "теории" или другого.

Я сделал бы следующее:

• преобразовывают каждый regex в FSA, с помощью чего-то как следующая структура:

  struct FSANode
  {
      bool accept;
      Map<char, FSANode> links;
  }
  List<FSANode> nodes;
  FSANode start;
  

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

• Делают новый Объединенный Узел как:

  class CombinedNode
  {
      CombinedNode(FSANode left, FSANode right)
      {
          this.left = left;
          this.right = right;
      }
  
      Map<char, CombinedNode> links;
      bool valid { get { return !left.accept || !right.accept; } }
  
      public FSANode left;
      public FSANode right;
  }
  

Создают ссылки на основе следующего тот же символ на левых и правых сторонах, и Вы получаете два FSANodes, которые делают новый CombinedNode.

Затем запускаются в CombinedNode (leftStart, rightStart), и находят набор охвата, и если существуют какие-либо недопустимые CombinedNodes, набор не является "ортогональным".