Минимальная форма автомата

Минимальный автомат — это автомат, имеющий наименьшее возможное количество состояний и реализующий заданную функцию выходов. Задача минимизации автомата сводится к поиску его минимальной формы. Для произвольного конечного автомата может быть построен эквивалентный ему конечный автомат с наименьшим числом состояний.

Принцип построенияПравить

Минимальная форма автомата S (обозначается как Š) в теории автоматов представляет собой автомат с ň состояниями, образующими множество {σ₁..σ_ň}. Минимальный автомат из S строится следующим образом. Характеристические функции автоматов S и Š обозначаются g_s, g_z и g'_s , g'_z соответственно. Тогда, если
$g_s({\mathrm{\xi <!--\; \xi \; -->}}_i,{\mathrm{\sigma <!--\; \sigma \; -->}}^{(u)})={\mathrm{\xi <!--\; \xi \; -->}}_j{g}_z({\mathrm{\xi <!--\; \xi \; -->}}_i,{\mathrm{\sigma <!--\; \sigma \; -->}}^{(u)})={\mathrm{\sigma <!--\; \sigma \; -->}}^{(v)}$${g_{s}(\xi _{i},\sigma ^{(u)})=\xi _{j}\qquad \qquad g_{z}(\xi _{i},\sigma ^{(u)})=\sigma ^{(v)}}$ , то
$g_s^{\prime }({\mathrm{\xi <!--\; \xi \; -->}}_i,{\mathrm{\sigma <!--\; \sigma \; -->}}^u)={\mathrm{\xi <!--\; \xi \; -->}}_j{g}_z^{\prime }({\mathrm{\xi <!--\; \xi \; -->}}_i,{\mathrm{\sigma <!--\; \sigma \; -->}}^u)={\mathrm{\sigma <!--\; \sigma \; -->}}^v$${g'_{s}(\xi _{i},\sigma ^{u})=\xi _{j}\qquad \qquad \ \;g'_{z}(\xi _{i},\sigma ^{u})=\sigma ^{v}}$ .

Таким образом, при построении Š по данному условию не возникает никакой неопределенности.

Алгоритм нахождения минимального автомата был предложен Ауфенкампом и Хоном. Ими было показано, что для нахождения минимального автомата необходимо находить последовательные разбиения P_i автомата S на классы 1, 2, …, k, (k+1) — эквивалентных между собой состояний, до тех пор пока на каком-то (k+1) шаге не окажется, что P_k = P_k+1. Таким образом, разбиение P_k дает все классы эквивалентности состояний автомата S. Всем состояниям S, принадлежащим классу эквивалентности Σ_l можно приписать общее обозначение, например, σ_l. Таким образом, автомат Š получается из автомата S путём «объединения» одинаково обозначенных состояний в одно состояние. Способы, которыми это объединение производится, существенно зависят от того, каким образом определен автомат — таблицей, графом или матрицей.

Способы получения минимальной формыПравить

Таблица переходовПравить

Если заданы таблица переходов и эквивалентное разбиение Σ₁..Σ_ň автомата S, то таблица переходов Š может быть построена следующим образом:

1. Заменить обозначение каждого состояния, имеющегося в таблице S на обозначение класса, которому данное состояние принадлежит.
2. Из каждой группы строк с одинаковыми обозначениями в клетках основного столбца вычеркнуть все строки, кроме одной.

Полученная при этом таблица является таблицей переходов Š.

Граф переходовПравить

Если заданы граф переходов (диаграмма состояний) и эквивалентное разбиение Σ₁..Σ_ň автомата S, то граф переходов Š может быть построен следующим образом:

1. Заменить обозначение каждого состояния, имеющегося в графе переходов S на обозначение класса, к которому относится данное состояние.
2. Объединить все одинаково обозначенные состояния (рассматривая дуги графа как «гибкие связи») и представить объединенные состояния одним состоянием, имеющим общее обозначение.
3. Из каждой группы дуг, имеющих общее исходное и общее конечное состояние вычеркнуть все, кроме одной.

Полученный в результате граф будет графом Š.

Матрица переходовПравить

Если заданы матрица переходов и эквивалентное разбиение Σ₁..Σ_ň автомата S, то матрица переходов Š может быть построена следующим образом:

1. Провести симметрическую перестановку и симметрическое разбиение [S] так, чтобы строки (и столбцы) группировались соответственно классам эквивалентности S (эту же матрицу можно получить при матричном методе эквивалентного разбиения).
2. Заменить все обозначения строк (и столбцов) каждой группы, представляющей класс эквивалентности, одним обозначением этого класса.
3. Заменить каждую подматрицу в разбитой матрице одной клеткой, содержащей все пары вход-выход, которые имеются в любой строке этой подматрицы (все строки в любой такой подматрице содержат одно и то же множество пар вход-выход).

Полученная в результате матрица является матрицей переходов Š.

Свойства минимальной формыПравить

Если Š является минимальной формой автомата S, то:

1. Š является единственной минимальной формой с точностью до обозначения состояний
2. Š=S
3. Никакие два состояния Š не являются эквивалентными
4. Не существует автомата, эквивалентного S и меньшего (с меньшим числом состояний), чем Š.

ЛитератураПравить

• Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966. - 272 с.
• Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.