Семинар 3. Эквивалентность автоматов

Эквивалентность автоматов. Язык автомата от произвольного состояния, эквивалентность состояний автоматов. Различающая строка неэквивалентной пары состояний. База: состояния, различимые по пустой строке. Шаг: пара, различимая по k символам, содержит общий переход в пару, различимую по k-1 символам. Длина различающей строки не превосходит N M. Решение за O(M^2 N^2 C): находим различимые пары в порядке увеличения длины различающей строки.

Декартово произведение автоматов. Бинарная функция над языками. Язык различающих строк и симметрическая языков. Достижимость множества доп. состояний. Эквивалентность автоматов: поиск в глубину по прямым рёбрам. Эквивалентные классы состояний: серия поисков в глубину по обратным рёбрам из доп. состояний. Минимальные различающие строки для пар состояний: обход в ширину по обратным рёбрам из множества доп. состояний. Время работы O(M N C).

Минимальный ДКА, эквивалентный данному. Удаление недостижимых состояний. Поиск пар эквивалентных состояний. Определение классов эквивалентности. Построение сжатого автомата. Доказательство минимальности полученного автомата (от противного). Время работы алгоритма: O(N^2 C).

Лемма о разрастании для ДКА. Применение к {0^n 1^n}, {a^p}.