Как минимизировать полностью определённые автоматы?

Для минимизации полностью определённых автоматов используется алгоритм, предложенный Ауфенкампом и Хоном. books.ifmo.ru Он состоит в разбиении всех состояний исходного абстрактного автомата на попарно непересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. books.ifmo.ru ppt-online.org

Алгоритм включает следующие шаги: ppt-online.org

1. Находится эквивалентное разбиение состояний на непересекающиеся классы эквивалентных состояний. ppt-online.org
2. В каждом классе эквивалентности разбиения выбирается по одному состоянию, в результате чего получается множество A состояний минимального автомата. ppt-online.org
3. Для определения функции переходов и функции выходов автомата в таблицах переходов и выходов вычёркиваются столбцы, соответствующие не вошедшим в A состояниям. ppt-online.org В оставшихся столбцах не вошедшие в множество А состояния заменяются на эквивалентные. ppt-online.org
4. В качестве начального состояния выбирается состояние, эквивалентное состоянию a1. ppt-online.org

Получающийся в результате минимизации автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата. ppt-online.org