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

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

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

Answer 3

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

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

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

Answer 4

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

Считаете ли вы два RE ортогональными, если они перекрываются каким-либо образом? Или, если один является подмножеством другого? Или просто, если их нельзя использовать для совпадения с одним и тем же текстом?

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

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