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