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

Понедельник, 21 февраля 2022
НГУ, ауд. 1156, НГУ, новый корпус

Описание

Эквивалентность автоматов. Язык автомата от произвольного состояния, эквивалентность состояний автоматов. Различающая строка неэквивалентной пары состояний. База: состояния, различимые по пустой строке. Шаг: пара, различимая по 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}.