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

Алгоритм включает следующие шаги: 4

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

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