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

Question

Полагаю, мой вопрос лучше всего объяснить на (упрощенном) примере.

Regex 1:

^\d+_[a-z]+$

Regex 2:

^\d*$

регулярное выражение 1 будет никогда соответствовать строке, где регулярное выражение 2 соответствует. Итак, допустим, что регулярное выражение 1 является ортогональным к регулярному выражению 2.

Как многие люди спрашивали, что я имел в виду под ортогональным Я постараюсь уточнить это:

Пусть S1 будет (бесконечным) набором строк, где соответствует регулярное выражение 1. S2 - это набор строк, в которых совпадает регулярное выражение 2. Регулярное выражение 2 ортогонально регулярному выражению 1 , если пересечение S1 и S2 пусто. Регулярное выражение ^ \ d_a $ будет не ортогональным , поскольку строка '2_a' находится в наборе S1 и S2.

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

В лучшем случае была бы библиотека, в которой реализован такой метод:

/**
 * @return True if the regex is orthogonal (i.e. "intersection is empty"), False otherwise or Null if it can't be determined
 */
public Boolean isRegexOrthogonal(Pattern regex1, Pattern regex2);

Answer 1

Под «ортогональным» вы подразумеваете «пересечение - это пустое множество». Я так понимаю?

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

Опять же, я теоретик ...

Answer 2

Прошло два года с тех пор, как этот вопрос был опубликован, но я рад сообщить, что это можно определить сейчас, просто вызвав программу "genex" здесь: https://github.com/audreyt/regex-genex

$ ./binaries/osx/genex '^\d+_[a-z]+$' '^\d*$'
$

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

$ runghc Main.hs '\d' '[123abc]' 
1.00000000      "2"
1.00000000      "3"
1.00000000      "1"

Надеюсь, это поможет!

Answer 3

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

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

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

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

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

Итак, учитывая то, что, я думаю, вы используете в качестве определения для ортогональности, если вы переводите свои RE в FSM, и эти FSM не равны, RE являются ортогональными.

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

---

Кроме того, помните, что конструкция \ 1, \ 2, ..., \ 9 не является регулярной: ее нельзя выразить через конкатенацию, объединение и * (звезда Клини). Если вы хотите включить обратную замену, я не знаю, каков ответ. Также представляет интерес тот факт, что соответствующая проблема для контекстно-свободных языков неразрешима: не существует алгоритма, который бы брал две контекстно-свободные грамматики G1 и G2 и возвращал бы значение true, если бы L (G1) ∩ L (g2) ≠ Ø.

Answer 4

Отличный момент для \ 1, \ 2 бита ... это контекстно-свободный, и поэтому не решаемый. Незначительный момент: не ВСЕ сводится к остановке ... Программа Эквивалентность, например .. - Брайан Постоу

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

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

Я изменяю свое утверждение: все в RE сводится к проблеме остановки; -)

Answer 5

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

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

Answer 6

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

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

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

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

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

Answer 7

Я наконец нашел именно ту библиотеку, которую искал:

dk.brics.automaton

Использование:

/**
 * @return true if the two regexes will never both match a given string
 */
public boolean isRegexOrthogonal( String regex1, String regex2 ) {
   Automaton automaton1 = new RegExp(regex1).toAutomaton();
   Automaton automaton2 = new RegExp(regex2).toAutomaton();
   return automaton1.intersection(automaton2).isEmpty();
}

Следует отметить, что реализация не поддерживает и не может поддерживать сложные функции RegEx, такие как обратные ссылки. См. Сообщение в блоге «Более быстрый пакет регулярных выражений Java» , в котором представлены dk.brics.automaton .

Answer 8

Конвертировать каждое регулярное выражение в DFA. Из состояния принятия одного DFA создайте эпсилон-переход в начальное состояние второго DFA. Фактически вы создадите NFA, добавив эпсилон-переход. Затем преобразовать NFA в DFA. Если начальное состояние не является состоянием принятия, а состояние принятия достижимо, то эти два регулярных выражения не являются «ортогональными». (Поскольку их пересечение не пусто.)

Существуют известные процедуры для преобразования регулярного выражения в DFA и преобразования NFA в DFA. Вы можете взглянуть на книгу типа «Введение в теорию вычислений» от Sipser, или просто поискать в Интернете. Без сомнения, многие старшекурсники и выпускники должны были сделать это для того или иного «теоретического» класса.

Answer 9

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

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

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

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

• Создайте новый комбинированный узел, например:

  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;
  }
  

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

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

Answer 10

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

Это правильно?