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

[anton_nazarov]

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

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

Comments

[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, пройдясь по пути. В противном случае такой строки нет.

[griffon]

Пусть выражение выглядит как A+. Строим DFA с одним принимающим состоянием для А. Добавляем эпсилон-переход из принимающего состояния в начальное, получая NFA для А+. Осталось применить стандартный алгоритм удаления эпсилон-переходов, чтобы получить DFА.

Если что-то непонятно, то советую почитать эту книгу .