Математический аппарат инженера - [39]

и М₂, находящиеся соответственно в начальных состояниях, σ_i и σ_j (обозначения М₁ и М₂ могут относиться к одному и тому же автомату), под воздействием любой входной последовательности выдают одинаковые выходные последовательности, т. е. автоматы М₁ и М₂ в данных состояниях σ_i и σ_j неразличимы по внешним выходам. Такое отношение между состояниями одного и того же или двух различных автоматов обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, оно является отношением эквивалентности состояний. Если состояния не эквивалентны, то их называют различимыми. Легко доказать справедливость следующих положений:

1) состояния σ_i и σ_j автомата явно различимы, если различаются соответствующие, им строки в таблице выходов;

2) состояния σ_i и σ_j автомата явно эквививалентны, если соответствующие им строки в таблице переходов и таблице выходов одинаковы или становятся одинаковыми при замене каждого номера σ_i на номер σ_j (или наоборот).

Например, для автомата, граф которого изображен на рис. 240, а, общая таблица переходов имеет вид:

- 573 -

Из этой таблицы следует, что состояния из множества {0, 3, 4}являются явно различимыми с любым состоянием из множества {1, 2, 5, 6}. Поэтому следует искать эквивалентные состояния только среди элементов, принадлежащих одному из этих множеств. Так как строки 0 и 4 одинаковы, а строки 1 и 5 становятся одинаковыми при замене цифры в числителе 1 на 5 (или 5 на 1), то явно эквивалентными являются пары состояний {0,4} И {1,5}.

Объединяя эквивалентные состояния в автомате М₁, получаем эквивалентный автомат М₂ с меньшим числом состоянии, который в любом состоянии нельзя отличить от исходного, наблюдая сигналы на выходах. Очевидно, автоматы М₁ и М₂ являются эквивалентными, если каждому состоянию σ_i , автомата М₁ соответствует, по крайней мере, одно эквивалентное ему состояние автомата M₂, и если каждому состоянию σ_j , автомата М₂ соответствует хотя бы одно эквивалентное ему состояние автомата М₁.

Эквивалентные состояния, например, σ_i и σ_j , удобно объединять по общей таблице переходов, вычеркивая строку σ_j , и заменяя везде в числителе числа σ_j на σ_i . После объединения пар явно эквивалентных состояний может оказаться возможным снова обнаружить такие состояния, которые также объединяются с помощью аналогичной процедуры. В результате последовательного объединения приходим к сокращенной таблице переходов, которой соответствует сокращенный автомат, эквивалентный исходному, но имеющий меньшее число состоянии. Так, для рассматриваемого примера получаем последовательно:

- 574 -

Первая таблица соответствует объединению пар эквивалентных состоянии {0,4} и {1, 5}, а вторая - объединению пары {2, 6}. Сокращенный автомат содержит только четыре состояния (рис.240, б).

8. Эквивалентное разбиение. Если известны все пары эквивалентных состояний конечного автомата, то тем самым на множестве S его состояний определено отношение эквивалентности, которому соответствует некоторое разбиение на классы эквивалентности S = {S₁, S₂ ..., S_ν}. При этом состояние, не имеющее эквивалентного ему состояния, составляет класс эквивалентности, единственным элементом которого является это состояние. Обозначим через σ^'₀, σ^'₁, ..., σ^'_ν представители классов эквивалентности и через М' – автомат, множеством состояний которого является семейство представителей S^' = {σ^'₀, σ^'₁, ..., σ^'_ν}. Можно утверждать, что автоматы М и М' эквивалентны (М ~ М'), причем М' имеет минимальное число состояний, т. е. является минцмальной формой автомата.

Объединение эквивалентных состояний в классы эквивалентности осуществляется весьма просто. Если σ_i ~ σ_j и σ_j ~ σ_k, то на основе свойства транзитивности следует, что σ_i ~ σ_k, и, значит, пары {σ_i , σ_j}и {σ_j , σ_k} входят в общий для них класс эквивалентности. Но для выявления всех пар эквивалентных состояний требуется более громоздкая процедура, так как множество таких пар не исчерпывается явно эквивалентными состояниями и не всегда может быть полностью обнаружено и объединено способом, изложенным ранее.

Для эквивалентного разбиения множества S состояний автомата предложен ряд способов. Один из них основан на последовательном рассмотрении всевозможных пар состояний и исключении тех из них, которые не являются эквивалентными. При этом пары одинаковых состояний {σ_i , σ_i}, являющиеся в силу свойства рефлективности заведомо эквивалентными {σ_i~σ_i}, не рассматриваются. Процедура эквивалентного разбиения осуществляется по таблице пар состояний, которая получается на основе общей таблицы переходов автомата. Так как явно различимые пары состояний (для таких состояний строки в таблице выходов различные) не могут быть эквивалентными, то они в таблицу пар не включаются. Для каждой пары отводится строка, для каждого входа – столбец, ав клетках на основании таблицы переходов указывается пара состояний, в которые переходит автомат из данной пары состояний при данном входном воздействии (порядок записи состояний в каждой паре безразличен). Исключаемые пары отмечаются каким-либо способом (набираются жирным шрифтом, подчеркиваются или снабжаются меткой). Далее приведены общая таблица переходов (табл. 10) и полученная из нее таблица пар состояний некоторого автомата.