10.7. Эквивалентное разбиение
Если
известны все пары эквивалентных
состояний конечного автомата, то тем
самым на множестве S
его состояний определено отношение
эквивалентности, которому соответствует
некоторое разбиение на классы
эквивалентности S
=
.
При этом состояние, не имеющее
эквивалентного ему состояния,
составляет класс эквивалентности,
единственным элементом которого
является это состояние. Обозначим через
представителей классов эквивалентности
и через М'
- автомат,
множеством состояний которого является
семейство представителей S'
= {
}.
Можно утверждать, что автоматы М
и М'
эквивалентны (М
~ М'),
причем М'
имеет минимальное число состоянии, т.е.
является минимальной
формой
автомата.
Объединение эквивалентных состояний
в классы эквивалентности осуществляется
весьма просто. Если
и
,
то на основе свойства транзитивности
следует, что
,
и, значит, пары {
}
и {
}
входят в общий для них класс эквивалентности.
Но для выявления всех пар эквивалентных
состояний требуется более громоздкая
процедура, так как множество таких пар
не исчерпывается явно эквивалентными
состояниями и не всегда может быть
полностью обнаружено и объединено
способом, изложенным в (10.6).
Для эквивалентного разбиения множества
S состояний автомата предложен ряд
способов. Один из них основан на
последовательном рассмотрении
всевозможных пар состояний и исключении
тех из них, которые не являются
эквивалентными. При этом пары одинаковых
состояний {
},
являющиеся в силу свойства рефлексивности
заведомо эквивалентными (
),
не рассматриваются. Процедура
эквивалентного разбиения осуществляется
по таблице пар состояний, которая
получается на основе общей таблицы
переходов автомата. Так как явно
различимые пары состояний (для таких
состояний строки в таблице выходов
различные) не могут быть эквивалентными,
то они в таблицу пар не включаются. Для
каждой пары отводится строка, для каждого
входа - столбец, а в клетках на основании
таблицы переходов указывается пара
состояний, в которые переходит автомат
из данной пары состояний при данном
входном воздействии (порядок записи
состояний в каждой паре безразличен).
Исключаемые пары отмечаются каким-либо
способом (набираются жирным шрифтом,
подчеркиваются или снабжаются меткой).
Ниже приведены общая таблица переходов
и полученная из нее таблица пар состояний
некоторого автомата:
-
x(v)
s(v)
0
1
2
x(v)
Пары
0
1
2
0
1/1
1/0
4/0
0,2
1,1
1,1
4,4
0,4
1,5
1,3
2,4
1
0/0
3/1
3/1
0,6
1,5
1,1
4,7
0,7
1,3
1,3
4,6
2
1/1
1/0
4/0
1,3
0,2
1,3
1,3
1,5
0,7
3,8
3,5
3
2/0
1/1
1/1
1,8
0,6
3,8
3,6
2,4
1,5
1,3
2,4
4
5/1
3/0
2/0
2,6
1,5
1,1
4,7
2,7
1,3
1,3
4,6
5
7/0
8/1
5/1
3,5
2,7
1,8
1,5
3,8
2,6
1,8
1,6
6
5/1
1/0
7/0
4,6
5,5
1,8
2,7
4,7
3,5
3,3
2,6
7
3/1
3/0
6/0
5,8
6,7
8,8
5,6
6,7
3,5
1,3
6,7
8
6/0
8/1
6/1
Так как одинаковые строки таблицы выходов соответствуют множествам состояний {0, 2, 4, 6, 7} и {1, 3, 5, 8}, то в первом столбце таблицы пар указаны только попарные комбинации таких состояний, которые входят в одно и то же множество, т. е. не являются явно различимыми.
Исключение пар основано на следующем
положении: если состояния
и
эквивалентны, то эквивалентными являются
и состояния, в которые автомат
переходит под любым входным воздействием.
Это значит, что на первом шаге необходимо
отметить те пары, которые переходят в
пары, состоящие из различных состояний
и отсутствующие в первой графе таблицы.
Так как обозначенные пары не могут быть
эквивалентными, то на следующем шаге
отмечаются все те пары, которые
переходят в пары, отмеченные на предыдущем
шаге и т. д. Процесс заканчивается тогда,
когда среди неотмеченных пар уже нет
таких, которые можно отметить в
соответствии с изложенным правилом.
После этого неотмеченные пары и
представляют собой попарно эквивалентные
состояния.
В приведенном примере на первом шаге
отмечаются пары {1, 8}, {3, 8} и {5, 8}, на втором
—{1,5} и {3, 5}, па третьем — {0, 4}, {0, 6}, {2, 4},
{2, 6}, {4,7} и {6, 7}. Эквивалентными являются
неотмеченные пары {0,2}, {0,7}, {1,3}, {2,7} и
{4,6}, образующие классы эквивалентности
= {0, 2, 7},
= {1, 3} и
= {4, 6}. Кроме того, не вошедшие в эти
множества состояния 5 и 8 образуют классы
эквивалентности
= {5} и
= {8}. Обозначив представителей
полученных пяти классов соответственно
числами от 0 до 4, получим для рассматриваемого
автомата минимальную форму с пятью
состояниями и общей таблицей переходов:
-
x(v)
s(v)
0
1
2
0
1/1
1/0
2/0
1
0/0
1/1
1/1
2
3/1
1/0
0/0
3
0/0
4/1
3/1
4
2/0
4/1
2/1
Следует отметить, что автомат, все состояния которого эквивалентны, сводится к автомату с одним состоянием, т. е. представляет собой по существу комбинационную схему. Автомат, среди состояний которого нет эквивалентных, является несократимым. Если М - минимальная форма автомата М, то она единственна и несократима.