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

Скажем, мы имеем регулярные выражения:

Hello W. * rld
Hello World
. * World
. * W. *

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

Чтобы сделать это, мне нужно найти, соответствует ли одно регулярное выражение любому входу, сопоставляемому другим выражением. Возможно ли это?

Billy3

Ответ 1

Любое регулярное выражение может быть связано с DFA - вы можете свести к минимуму DFA, и поскольку минимальная форма уникальна, вы можете решить, эквивалентны ли два выражения. Дани Крико указал на алгоритм Hopcroft O (n log n). Существует еще один улучшенный алгоритм Hopcroft и Craft, который проверяет эквивалентность двух DFA в O (n).

Для хорошего обзора по этому вопросу и интересного подхода к этому, я рекомендую документ Тестирование эквивалентности обычных языков, из arXiv.

Далее отредактируйте: если вы заинтересованы в включении, а не в эквивалентности для регулярных выражений, я столкнулся с документом, который может представлять интерес: Проблема включения для регулярных выражений Выражения - я только просмотрел его, но, похоже, он содержит полиномиальный алгоритм времени.

Ответ 2

Да.

Проблема эквивалентности двух регулярных языков разрешима.

Эскиз алгоритма:

минимизировать оба DFA
проверьте, являются ли они изоморфными

Ответ 3

Конечно!. Регулярное выражение может быть представлено как FSM (конечный автомат) и существует технически бесконечное число FSM, которое может распознавать одну и ту же строку.

Изоморфизм - это имя, которое описывает, если два FSM эквивалентны. Есть несколько алгоритмов для минимизации FSM. Например, алгоритм минимизации Hopcroft может минимизировать два FSM в O (n log n) на n-го автомата.

Ответ 4

Эта проблема называется "включение" или "подчинение" регулярных выражений, потому что то, о чем вы просите, заключается в том, включает ли набор слов, сопоставленных одному регулярному выражению, (или включает) набор слов, сопоставленных другому регулярному выражению. Равенство - это другой вопрос, который обычно означает, что два регулярных выражения соответствуют точно таким же словам, т.е. Что они функционально эквивалентны. Например, "a *" включает "aa *", хотя они не равны.

Все известные алгоритмы включения regexp - это худший случай, имеющий экспоненту времени в размере регулярного выражения. Но стандартный алгоритм выглядит так:

Входные данные r1 и r2 Выход Да, если r1 включает r2

Создать DFA (r1) и DFA (r2)
Создать Neg (DFA (r1)) (который соответствует именно этим словам, r1 не совпадает)
Создать Neg (DFA (r1)) x DFA (r2) (который соответствует точно таким словам, которые соответствуют Neg (DFA (r1)) и DFA (r2))
Убедитесь, что автомат, сделанный в 3., не соответствует ни одному слову

Это работает, поскольку то, что вы проверяете, заключается в том, что нет слов, сопоставленных с r2, которые не соответствуют r1.