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

Ответ 1

Попытка найти сложность этой проблемы привела меня к этой статье.

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

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

В этой статье есть отличная информация (резюме: все, кроме простейших выражений, довольно сложны), однако поиск информации о проблеме включения приводит непосредственно к fooobar.com/questions/165382/.... В этом ответе уже была ссылка на документ, описывающий алгоритм пассивного полиномиального времени, который должен охватывать множество распространенных случаев.

Ответ 2

Если регулярные выражения используют "расширенные функции" типичных процедурных совпадений (например, в 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 possible to eliminate r

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

Все это было разработано в 1960 году и в настоящее время является частью любого курса теории теории вычислительной техники. Золотой стандарт для этой темы Хопкрофт и Ульман, Теория автоматов.

Ответ 3

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

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

• Вычислить минимальный 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.
• В конце вы изучаете достижимые состояния:
  • Если есть пара [accepting, rejecting], то M2 не является подмножеством M1
  • Если есть пара [отклонение, переход], то M1 не является подмножеством M2

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

Ответ 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 делает (или может сделать) эту гарантию.

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