Эквивалентное разбиение
Если известны все пары эквивалентных состояний конечного автомата, то тем самым на множестве S его состояний определено отношение эквивалентности, которому соответствует некоторое разбиение на классы эквивалентности S = {S1, S2 ..., S}. При этом состояние, не имеющее эквивалентного ему состояния, составляет класс эквивалентности, единственным элементом которого является это состояние. Обозначим через '0, '1, ..., ' представители классов эквивалентности и через М' – автомат, множеством состояний которого является семейство представителей S' = {'0, '1, ..., '}. Можно утверждать, что автоматы М и М' эквивалентны (М ~ М'), причем М' имеет минимальное число состояний, т. е. является минцмальной формой автомата.
Объединение эквивалентных состояний в классы эквивалентности осуществляется весьма просто. Если i ~ j и j ~ k, то на основе свойства транзитивности следует, что i ~ k, и, значит, пары {i , j} и {j , k} входят в общий для них класс эквивалентности. Но для выявления всех пар эквивалентных состояний требуется более громоздкая процедура, так как множество таких пар не исчерпывается явно эквивалентными состояниями и не всегда может быть полностью обнаружено и объединено способом, изложенным ранее.
Для эквивалентного разбиения множества S состояний автомата предложен ряд способов. Один из них основан на последовательном рассмотрении всевозможных пар состояний и исключении тех из них, которые не являются эквивалентными. При этом пары одинаковых состояний {i , i}, являющиеся в силу свойства рефлективности заведомо эквивалентными {i~i}, не рассматриваются. Процедура эквивалентного разбиения осуществляется по таблице пар состояний, которая получается на основе общей таблицы переходов автомата. Так как явно различимые пары состояний (для таких состояний строки в таблице выходов различные) не могут быть эквивалентными, то они в таблицу пар не включаются. Для каждой пары отводится строка, для каждого входа – столбец, а в клетках на основании таблицы переходов указывается пара состояний, в которые переходит автомат из данной пары состояний при данном входном воздействии (порядок записи состояний в каждой паре безразличен). Исключаемые пары отмечаются каким-либо способом (набираются жирным шрифтом, подчеркиваются или снабжаются меткой). Далее приведены общая таблица переходов (табл. 10) и полученная из нее таблица пар состояний некоторого автомата (табл. 11).
Таблица 10
x() s() |
0 |
1 |
2 |
0 |
1/1 |
1/0 |
4/0 |
1 |
0/0 |
3/1 |
3/1 |
2 |
1/1 |
1/0 |
4/0 |
3 |
2/0 |
1/1 |
1/1 |
4 |
5/1 |
3/0 |
2/0 |
5 |
7/0 |
8/1 |
5/1 |
6 |
5/1 |
1/0 |
7/0 |
7 |
3/1 |
3/0 |
6/0 |
8 |
6/0 |
8/1 |
6/1 |
Таблица 11
x() Пары |
0 |
1 |
2 |
0,2 |
1,1 |
1,1 |
4,4 |
0,4 |
1,5 |
1,3 |
2,4 |
0,6 |
1,5 |
1,1 |
4,7 |
0,7 |
1,3 |
1,3 |
4,6 |
1,3 |
0,2 |
1,3 |
1,3 |
1,5 |
0,7 |
3,8 |
3,5 |
1,8 |
0,6 |
3,8 |
3,6 |
2,4 |
1,5 |
1,3 |
2,4 |
2,6 |
1,5 |
1,1 |
4,7 |
2,7 |
1,3 |
1,3 |
4,6 |
3,5 |
2,7 |
1,8 |
1,5 |
3,8 |
2,6 |
1,8 |
1,6 |
4,6 |
5,5 |
1,3 |
2,7 |
4,7 |
3,5 |
3,3 |
2,6 |
5,8 |
6,7 |
8,8 |
5,6 |
6,7 |
3,5 |
1,3 |
6,7 |
Так как одинаковые строки таблицы выходов соответствуют множествам состояний {0, 2, 4, 6, 7} и {1, 3, 5, 8}, то в первом столбце таблицы пар указаны только попарные комбинации таких состояний, которые входят в одно и то же множество, т. е. не являются явно различимыми.
Исключение пар основано на следующем положении: если состояния i и j эквивалентны, то эквивалентными являются и состояния, в которые автомат переходит под любым входным воздействием. Это значит, что на первом шаге необходимо отметить те пары, которые переходят в пары, состоящие из различных состояний и отсутствующие в первой графе таблицы. Так как обозначенные пары не могут быть эквивалентными, то на следующем шаге отмечаются все те пары, которые переходят в пары, отмеченные на предыдущем шаге и т. д. Процесс заканчивается тогда, когда среди неотмеченных пар уже нет таких, которые можно отметить в соответствии с изложенным правилом. После этого неотмеченные пары и представляют собой попарно эквивалентные состояния.
В приведенном примере на первом шаге отмечаются пары {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}, образующие классы эквивалентности S0 = {0, 2, 7}, S1 = { 1, 3} и S2 = { 4, 6}. Кроме того, не вошедшие в эти множества состояния 5 и 8 образуют классы эквивалентности S3 = {5} и S4 = {8}. Обозначив представителей полученных пяти классов соответственно числами от 0 до 4, получим для рассматриваемого автомата минимальную форму с пятью состояниями и общей таблицей переходов (табл. 12).
Таблица 12
x() s() |
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/0 |
2/1 |
Следует отметить, что автомат, все состояния которого эквивалентны, сводится к автомату с одним состоянием, т. е. представляет собой по существу комбинационную схему. Автомат, среди состояний которого нет эквивалентных, является несократимым. Если М' – минимальная форма автомата М, то она единственна и несократима.