Интересный вопрос про алгоритмы

[anton_nazarov]

Вчера возник такой занятный вопрос.
Существует ли алгоритм, который за конечное время по двум регекспам определяет, является ли множество строк, матчимых одним подмножеством строк, матчимых другим?
А для perl-овских регекспов?

P.S.
Думать и гуглить не пробовал.

Comments

[krlz]

Можно привести оба регэкспа к детерминированному конечному автомату, и проверить их на изоморфность.

[anton_nazarov]

А это правда, что автомат для "меньшего" регекспа будет подавтоматом для "большего"?

[krlz]

Интуитивно кажется что да, но нужно, конечно строго доказывать.

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

[griffon]

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

Пусть мы хотим проверить, правда ли, что второй регексп мэтчит подмножество первого. Строим два DFA так, чтобы у них было по одному принимающему состоянию (f_1 и f_2 соответственно). Теперь по ним строим граф, в вершинах которого стоят пары (s_1, s_2) --- пары состояний, s_1 --- первого автомата, s_2 --- второго. Ребро между вершиной (s_1, s_2) и (s'_1, s'_2) проводим, если есть символ, по которому первый автомат переходит из s_1 в s'_1, а второй из s_2 в s'_2. Запускаем какой-нибудь обход (DFS, BFS) из вершины, соответствующей паре начальных состояний. Ну и наконец проверяем, что все вершины, соответствующие паре (x, f_2), где x не равно f_1 недостижимы. Это равносильно тому, что второй регексп мэтчит подмножество первого.

[griffon]

Второй регэксп это подмножество первого. Так что во второй паре надо, чтобы было (x, t_3), а не (s_3, x).

Последнее предложение следует понимать так: второй регэксп мэтчит подмножество первого тогда и только тогда, когда состояния вида (x, f_2), где x не равно f_1, недостижимы. Если какое-то такое состояние достижимо, то мы легко построим строку, котороая мэтчится s_2 и не мэтчится s_1, пройдясь по пути. В противном случае такой строки нет.

[crimeanelf]

>матчимых одним подмножеством...

Долго думала над незнакомым словом. Следует читать как "совпадающих с одним подмножеством"?

[abreslav]

Я пробежался по комментам: ответа не увидел. Если он там был, извиняйте.

1. Для регулярных языков можно проверить включение. Делается это так: берем один автомат (входной) и "запускаем" не нем другой: то, что один гененрирует, второй распознает. Запоминпем, в каких состояниях оказывается распознающий автомат, для каждого состояния входного. Считаем до неподвижной точки. Она есть, потому что состояний конечное число. Все.

2. Перловые регэкспы описывают нерегулярные языки и для них ничего нельзя.

[abreslav]

Это, наверное, то же самое, что выше предложил griffon, но мне лень проверять

[anton_nazarov]

Правильно ли я понял, что в пункте 1 предлагает генерировать все строки, которые матчатся одним из регэкспов? Как быть с конечностью времени работы?

[abreslav]

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

Я опять плохо объяснил, но лучше (если коротко) пока не придумал.