Определение того, является ли регулярное выражение подмножеством другого

Question

У меня есть большая коллекция регулярных выражений, которая при сопоставлении вызывает конкретный обработчик http. Некоторые из старых регулярных выражений недостижимы (например, a.c* ⊃ abc*), и я бы хотел их обрезать.

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

Я не был уверен, что это было разрешимо сначала (это пахло как проблема с остановкой другим именем). Но получается it's decidable.

Answer 1

В разделе математики есть ответ: https://math.stackexchange.com/questions/283838/is-one-regular-language-subset-of-another.

Основная идея:

• Compute минимальный DFA для обоих языков.
• Рассчитайте поперечное произведение двух автоматических автоматов M1 и M2, что означает, что каждое состояние состоит из пары [m1, m2], где m1 от M1 и m2 от M2 для всех возможных комбинаций.
• Новый переход F12: F12 ([m1, m2], x) => [F1 (m1, x), F2 (m2, x)]. Это означает, что при переходе в M1 из состояния m1 в m1 'при чтении x и в M2 от состояния m2 до m2' при чтении x, тогда есть один переход в M12 от [m1, m2] до [m1 ', m2' ] при чтении x.
• В конце вы смотрите в достижимости состояний:
  • Если есть пара [принятия, отвергая], то M2 не является подмножеством M1
  • Если есть пара [отвергая, accapting] то M1 не является подмножество М2

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

Answer 2

Trying to find the complexity of this problem lead me to this paper.

Формальное определение проблемы можно найти в: это, как правило, называют проблема включения

Проблема включения для R, чтобы проверить на два заданных выражения г, r '∈ R, ли r ⊆ r'.

Этого документ имеет много информации (сводной: все, кроме самых простых выражений довольно сложно), однако поиска информации о проблеме включения приводит один непосредственно к StackOverflow. У этого ответа уже была ссылка на a paper describing a passable polynomial time algorithm, которая должна охватывать множество распространенных случаев.

Answer 3

Если в регулярных выражениях используются «расширенные функции» типичных процедурных совпадений (например, в Perl, Java, Python, Ruby и т. Д.), Которые позволяют принимать языки, которые не являются регулярными, тогда вам не повезло. Проблема вообще неразрешима. Например. проблема того, распознает ли один пусковой автомат один и тот же контекстный свободный (CF) язык, поскольку другой является неразрешимым. Расширенные регулярные выражения могут описывать языки CF.

С другой стороны, если в теоретическом смысле регулярные выражения являются «истинными», состоящими только из конкатенации, чередования и звезды Клейна над строками с конечным алфавитом, плюс обычный синтаксический сахар на этих (классы символов, +,? и т. д.), тогда существует простой полиномиальный алгоритм времени.

Я не могу дать вам библиотеки, но это:

For each pair of regexes r and s for languages L(r) and L(s) 
    Find the corresponding Deterministic Finite Automata M(r) and M(s) 
    Compute the cross-product machine M(r x s) and assign accepting states 
     so that it computes L(r) - L(s) 
    Use a DFS or BFS of the the M(r x s) transition table to see if any 
     accepting state can be reached from the start state 
    If no, you can eliminate s because L(s) is a subset of L(r). 
    Reassign accepting states so that M(r x s) computes L(s) - L(r) 
    Repeat the steps above to see if it's possible to eliminate r 

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

Все это было разработано в 1960-х годах и в настоящее время является частью любого курса теории теории вычислительной техники. Золотой стандарт для этой темы - Hopcroft and Ullman, Automata Theory.

Answer 4

Я нашел библиотеку регулярных выражений python, которая предоставляет заданные операции.

http://github.com/ferno/greenery

Доказательство говорит Sub ⊆ Sup ⇔ Sub ∩ ¬Sup is {}. Я могу это реализовать с помощью библиотеки Python:

import sys 
from greenery.lego import parse 

subregex = parse(sys.argv[1]) 
supregex = parse(sys.argv[2]) 

s = subregex&(supregex.everythingbut()) 
if s.empty(): 
    print("%s is a subset of %s"%(subregex,supregex)) 
else: 
    print("%s is not a subset of %s, it also matches %s"%(subregex,supregex,s) 

примеры:

subset.py abcd.* ab.* 
abcd.* is a subset of ab.* 

subset.py a[bcd]f* a[cde]f* 
a[bcd]f* is not a subset of a[cde]f*, it also matches abf* 

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

В стороне: Игра с библиотекой для расчета обратных или упрощенных регулярных выражений - это очень весело.
a(b|.).* упрощает до a.+. Это довольно мало.
Обратный код abf*: ([^a]|a([^b]|bf*[^f])).*|a?. Постарайтесь придумать это самостоятельно!