Математический аппарат инженера - страница 49
 |  |
- 574 -
Первая таблица соответствует объединению пар эквивалентных состоянии {0,4} и {1, 5}, а вторая - объединению пары {2, 6}. Сокращенный автомат содержит только четыре состояния (рис.240, б).
8. Эквивалентное разбиение. Если известны все пары эквивалентных состояний конечного автомата, то тем самым на множестве S его состояний определено отношение эквивалентности, которому соответствует некоторое разбиение на классы эквивалентности S = {S>1, S>2 ..., S>ν}. При этом состояние, не имеющее эквивалентного ему состояния, составляет класс эквивалентности, единственным элементом которого является это состояние. Обозначим через σ>'>0, σ>'>1, ..., σ>'>ν представители классов эквивалентности и через М' – автомат, множеством состояний которого является семейство представителей S>' = {σ>'>0, σ>'>1, ..., σ>'>ν}. Можно утверждать, что автоматы М и М' эквивалентны (М ~ М'), причем М' имеет минимальное число состояний, т. е. является минцмальной формой автомата.
Объединение эквивалентных состояний в классы эквивалентности осуществляется весьма просто. Если σ>i ~ σ>j и σ>j ~ σ>k, то на основе свойства транзитивности следует, что σ>i ~ σ>k, и, значит, пары {σ>i , σ>j}и {σ>j , σ>k} входят в общий для них класс эквивалентности. Но для выявления всех пар эквивалентных состояний требуется более громоздкая процедура, так как множество таких пар не исчерпывается явно эквивалентными состояниями и не всегда может быть полностью обнаружено и объединено способом, изложенным ранее.
Для эквивалентного разбиения множества S состояний автомата предложен ряд способов. Один из них основан на последовательном рассмотрении всевозможных пар состояний и исключении тех из них, которые не являются эквивалентными. При этом пары одинаковых состояний {σ>i , σ>i}, являющиеся в силу свойства рефлективности заведомо эквивалентными {σ>i~σ>i}, не рассматриваются. Процедура эквивалентного разбиения осуществляется по таблице пар состояний, которая получается на основе общей таблицы переходов автомата. Так как явно различимые пары состояний (для таких состояний строки в таблице выходов различные) не могут быть эквивалентными, то они в таблицу пар не включаются. Для каждой пары отводится строка, для каждого входа – столбец, ав клетках на основании таблицы переходов указывается пара состояний, в которые переходит автомат из данной пары состояний при данном входном воздействии (порядок записи состояний в каждой паре безразличен). Исключаемые пары отмечаются каким-либо способом (набираются жирным шрифтом, подчеркиваются или снабжаются меткой). Далее приведены общая таблица переходов (табл. 10) и полученная из нее таблица пар состояний некоторого автомата.
- 575 -
Так как одинаковые строки таблицы выходов соответствуют множествам состояний {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}, образующие классы эквивалентности S>0 = {0, 2, 7}, S>1 = { 1, 3} и S>2 = { 4, 6}. Кроме того, не вошедшие в эти множества состояния 5 и 8 образуют классы эквивалентности S