Здравствуйте, Sinclair, Вы писали:

S>2. Можно попытаться ввести на пространстве регексов отношения частичного порядка, типа regA < regB если для любого текста T, который матчится по regB, regA тоже гарантированно будет матчить. Тогда можно проверить ручное ранжирование на предмет этой упорядоченности, т.к. если "следующее" правило < "предыдущего", то "следующее" не сработает никогда.

S>Вопрос о вычислении этого частичного порядка, имхо, достаточно сложен. Простые примеры тут уже привели; но есть масса несложных примеров, когда это не сработает.

Задача об эквивалентности(а также "включенности", и поиска пересечения языков) двух КА (все равно (НКА или ДКА)/регеспов) полиномиален. Достаточно рассмотреть декартово произведение двух автоматов: состояние — упорядоченная пара <состояние автомата1, состояние автомата2>, переход из <a11, a21> в <a12, a22> по символу Х <=> имеется переход для автомата1 из a11 в a12 по Х, и имеется переход для автомата2 из a21 в а22 по Х.

Гарантируется, что состояние <старт1, страрт2> "достижимо". Далее каким-нибудь обходом графа (BFS/DFS) заполняется таблица достижимых состояний для произведения автоматов.

Если из того, что <X, Y> достижимо в новом автомате и X — заключительное состояние автомата1 следует, что Y — заключительное состояние автомата2, То автомат2 распознает как минимум язык автомата1. Для эквивалентности нужно еще и в другую сторону. И т.д.