Минимальный автомат — это автомат, имеющий наименьшее возможное количество состояний и реализующий заданную функцию выходов. Задача минимизации автомата сводится к поиску его минимальной формы. Для произвольного конечного автомата может быть построен эквивалентный ему конечный автомат с наименьшим числом состояний[1].
Минимальная форма автомата S (обозначается как Š) в теории автоматов представляет собой автомат с ň состояниями, образующими множество {σ1..σň}. Минимальный автомат из S строится следующим образом. Характеристические функции автоматов S и Š обозначаются gs, gz и g's , g'z соответственно. Тогда, если
, то
.
Таким образом, при построении Š по данному условию не возникает никакой неопределенности.
Алгоритм нахождения минимального автомата был предложен Ауфенкампом и Хоном. Ими было показано, что для нахождения минимального автомата необходимо находить последовательные разбиения Pi автомата S на классы 1, 2, …, k, (k+1) — эквивалентных между собой состояний, до тех пор пока на каком-то (k+1) шаге не окажется, что Pk = Pk+1. Таким образом, разбиение Pk дает все классы эквивалентности состояний автомата S. Всем состояниям S, принадлежащим классу эквивалентности Σl можно приписать общее обозначение, например, σl. Таким образом, автомат Š получается из автомата S путём «объединения» одинаково обозначенных состояний в одно состояние. Способы, которыми это объединение производится, существенно зависят от того, каким образом определен автомат — таблицей, графом или матрицей.
Если заданы таблица переходов и эквивалентное разбиение Σ1..Σň автомата S, то таблица переходов Š может быть построена следующим образом:
Полученная при этом таблица является таблицей переходов Š.
Если заданы граф переходов (диаграмма состояний) и эквивалентное разбиение Σ1..Σň автомата S, то граф переходов Š может быть построен следующим образом:
Полученный в результате граф будет графом Š.
Если заданы матрица переходов и эквивалентное разбиение Σ1..Σň автомата S, то матрица переходов Š может быть построена следующим образом:
Полученная в результате матрица является матрицей переходов Š.
Если Š является минимальной формой автомата S, то:
Для улучшения этой статьи желательно: |