регулярное выражение «содержит» другое регулярное выражение

Question

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

RegEX1 = "a.*b";
RegEx2 = "a1.*b";

RegEX1 "содержит" RegEX2.

Насколько я знаю - это невозможно, я не прав? <Ч /> Хорошо, joel.neely показал, что это можно сделать (еще не читал ...) в учебе.

Можно ли это сделать на языке программирования, скажем C #?
Насколько это будет эффективно? Сколько времени займет тестирование 1000 пар?

Answer 1

Да.

Этот документ содержит подробное обсуждение темы (см. Раздел 4.4).

Answer 2

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

Это сработало бы только для «простых» регулярных выражений (или реальных, что у вас, рекурсивные выражения perls гораздо более выразительны).

Хотя граф конечного автомата может иметь большое количество путей, он все равно должен быть ограничен (особенно, если источником выражений является человек). Таким образом, вы найдете все допустимые пути RegEX1 и по очереди по очереди проверьте, допустимо ли это в RegEX2. Если все пути допустимы, вы знаете, что один из них содержится в другом.