6.2. Изоморфизм и эквивалентность автоматов

Пусть S=(A_S, Q_S, V_S, _S, _S,) и Т=(A_T, Q_T, V_T, _T, _T,) – два автомата.

Тройка отображений f: A_S A_T; g: Q_S Q_T; h: V_S V_T называется гомоморфизмом автомата S в автомат Т, если при любых aA_S, qQ_S, VV_{S ­}выполнены условия:

_T(g(q),f(a))=g(_S(q,a));

_T (g(q),f(a))=h(_T(q,a)).

Автомат Т называют гомоморфным автомату S. Если кроме того, эти три отображения взаимно однозначны, то они называются изоморфизмом S на Т. Автоматы, для которых существует изоморфизм называют изоморфными. Мощности соответствующих алфавитов изоморфных автоматов доложны быть одинаковыми. Автоматы S и Т изоморфны, если входы, выходы и состояния S можно переименовать так, что таблица переходов автомата S превратится в таблицу переходов Т. Изоморфизм графов переходов является необходимым, но не достаточным условием изоморфизма соответствующих автоматов.

П ример 4: Пусть автомат Т имеет граф переходов:

Поменяем местами буквы на ребрах (r₁, r₂) и (r₂, r₁). Получим автомат Т', граф которого изоморфен графу Т, однако сам автомат Т' не изоморфен Т. Действительно, при изоморфизме графов вершина r₄ автомата Т изоморфна вершине r₄ автомата Т', однако Т(r₄,ааа)=VVV, Т' (r₄,ааа)=VVW,

Пусть S и Т – два автомата с одинаковыми входными и выходными алфавитами. Состояние q автомата S и состояние r автомата Т называются неотличимыми, если для любого входного слова : S(q, )= T(r, ).

Неотличимость состояний q_i и q_j одного автомата S означает, что инициальные автоматы (S,q_i) и (S,q_j) реализуют одно и то же автоматное отображение.

Автоматы S и Т называют неотличимыми или эквивалентными, если для любого состояния q автомата S найдется неотличимое от него состояние r автомата Т и, наоборот, для любого состояния r автомата T найдется неотличимое от него состояние q автомата S. Неотличимость автоматов означает, что любое автоматное отображение, реализуемое одним из них, может быть реализовано другим.

Ставится задача: среди автоматов, эквивалентных S, найти автомат с наименьшим числом состояний – минимальный автомат.

Наиболее известным алгоритмом нахождения эквивалентных состояний является алгоритм Мили:

Пусть дан автомат S=(A,Q,V,,) c n состояниями. На любом шаге алгоритма будем строить некоторое разбиение Q на классы, причем разбиение на следующем шаге будет получаться путем расщепления некоторых классов предыдущего разбиения.

Шаг1: Два состояния q и q' относим в один класс с_j, тогда и только тогда, когда aA: (q,a)= (q',a)

Шаг(i+1): Два состояния q и q' относим в один класс с_i+1,j, тогда и только тогда, когда aA: (q,a) и (q',a) принадлежат к одному и тому же классу с_i,j. Если (i+1) шаг не изменяет разбиения, то алгоритм заканчивается и полученное разбиение является разбиением на классы эквивалентных состояний.

В нашем примере вычеркиваются строки 4, 8, 7; в клетках полученной таблицы 4 заменяем на 1; 8 на 2; 7 на 5. В результате получим таблицу.

Таблица 22

qi	a1	a2	a3
1	2,0	1,1	1,1
2	1,1	1,0	5,0
3	1,1	6,0	5,0
5	6,1	1,1	3,0
6	2,0	9,1	6,1
9	5,0	9,1	5,1

Автомат, заданный представленной таблицей будет эквивалентным данному исходному автомату.