Правила перехода между моделями Мили и Мура

Для каждого автомата Мура может быть найден эквивалентный ему автомат Мили, и наоборот. Рассмотрим правила перехода между этими двумя моделями.

I.Переход от модели Мура к модели Мили.

1. Входной и выходной алфавиты, множество состояний и таблица переходов автомата Мили те же, что и для автомата Мура.

2. Выходной сигнал автомата Мили, формируемый при переходе в состояние a_i, совпадает с выходным сигналом, которым отмечено состояние a_i в автомате Мура (табл. 5.3, 5.4).

II. Переход от модели Мили к модели Мура.

1. Входной и выходной алфавиты совпадают.

2. Формируется промежуточная таблица, в которой каждой паре автомата Мили x_ia_j ставится в соответствие состояние автомата Мура b_ij. Кроме того, начальному состоянию автомата Мили ставится в соответствие начальное состояние автомата Мура b₀.

3. Строится таблица переходов автомата Мура, которая заполняется следующим образом. Каждое состояние b_ij отмечается выходным сигналом, записанным в ячейке автомата Мили на пересечении i-й строки и j-го столбца. Последующими для состояний автомата Мура будут состояния из промежуточной таблицы, записанные в столбце с номером a_k, где a_k – состояние автомата Мили, записанное в таблице переходов автомата Мили в ячейке на пересечении i-й строки и j-го столбца.

4. Последующими состояниями для b₀ будут последующие состояния для начального состояния автомата Мили в промежуточной таблице. Состояние b₀ отмечается таким выходным сигналом, чтобы столбец b₀ совпал с каким-либо другим столбцом таблицы переходов автомата Мура (табл. 5.5 – 5.7).

Рассмотрим примеры.

1. Автомат Мура → автомат Мили.

Таблица 5.3

2. Автомат Мили → автомат Мура.

Таблица 5.5 Таблица 5.6

Таблица 5.7

Пусть выходной сигнал для состояния b₀ такой же, как и для состояния b₁₂. Тогда столбец b₀ полностью совпадает со столбцом b₁₂ и, следовательно, эти два состояния могут быть представлены одним, которое обозначим b₀. При этом столбец b₁₂ может быть удален из таблицы, а все переходы в состояние b₁₂ должны быть изменены на переходы в b₀.

5.2. Минимизация числа состояний
цифровых автоматов

В общем случае таблица переходов ЦА, полученная тем или иным способом, может содержать избыточное число состояний. Поскольку от количества состояний абстрактного автомата зависит число элементов памяти, используемых при структурном синтезе ЦА, ставится задача сокращения избыточных состояний ЦА. При этом процесс минимизации числа состояний заключается в исключении некоторых состояний абстрактного автомата, а также в замене ряда состояний одним таким образом, чтобы получившийся в результате автомат был эквивалентен исходному, т.е. на одинаковую последовательность входных сигналов оба автомата (исходный и минимизированный, находящиеся в начальном состоянии) должны отвечать одинаковыми последовательностями выходных сигналов.

Рассмотрим приемы, позволяющие проводить предварительное сокращение числа состояний.

Во-первых, из таблицы переходов можно удалить все недостижимые состояния, т.е. такие, в которые автомат не сможет попасть из начального состояния под воздействием любой последовательности входных сиг­налов.

Во-вторых, из таблицы переходов автомата Мили можно исключить все состояния, которым соответствуют столбцы таблицы переходов, содержащие в своих ячейках только прочерки, т.е. неопределенные состояния перехода. При этом все вхождения исключенных по данному правилу состояний в упрощенной таблице переходов заменяются прочерками.

В-третьих, из таблицы переходов автомата Мура могут быть исключены все столбцы, соответствующие состояниям, отмеченным неопределенными выходными сигналами. Вхождения исключенных состояний в упрощенную таблицу переходов заменяются прочерками.

Кроме того, каждая группа состояний, которой соответствуют одинаковые столбцы таблицы переходов, может быть заменена одним из состояний группы, при этом все вхождения исключенных состояний в таблице переходов заменяются на состояние, номер которого представляет группу одинаковых столбцов.

Рассмотрим пример. Сформируем упрощенную таблицу переходов автомата, заданного табл. 5.8.

Таблица 5.8

В этой таблице одинаковые столбцы соответствуют состояниям (1, 3) и (2, 7). Введем обозначения: группа состояний (1, 3) – 1, группа (2, 7) – 2.

Тогда столбцы табл. 5.8, соответствующие состояниям 3 и 7, можно исключить, а все вхождения этих состояний заменить состояниями 1 и 2 соответственно. В результате получим упрощенную таблицу переходов (табл. 5.9).

Таблица 5.9

5.2.1. Минимизация числа состояний синхронного автомата
методом Полла-Ангера

Будем полагать, что подлежащий минимизации автомат является синхронным автоматом Мили и дальнейшее сокращение числа его состояний с использованием вышеописанных приемов невозможно.

Совокупность состояний таблицы переходов, представляемых состоянием какой-либо другой таблицы переходов, будем называть совместимым множеством или множеством совместимых состояний. Задача минимизации заключается в нахождении множеств совместимых состояний с последующей заменой каждого из множеств одним состоянием.

Рассмотрим условия, которым должны удовлетворять совместимые состояния.

Первое условие совместимости – формирование непротиворечивых выходных сигналов при одинаковой входной переменной. Это означает, что в тех строках, где выходные сигналы определены, они должны совпадать. В табл. 5.10 состояния 1 и 2 являются совместимыми по выходам. Также совместимыми по выходам являются пары состояний 2, 3; 2, 4; 3, 4.

Таблица 5.10

Второе условие совместимости состояний заключается в том, что переходы из этих состояний под воздействием одинакового входного сигнала должны осуществляться в одинаковые состояния, если оба они определены. Пара состояний 1, 2 удовлетворяет этому условию, так как под воздействием всех входных сигналов осуществляются переходы в одинаковые состояния. Пара состояний 2, 4 не удовлетворяет второму условию совместимости, так как под воздействием входного сигнала х₁ автомат переходит из состояний 2, 4 в состояния 2, 1.

Пары состояний, подобные 2, 4, называются условно совместимыми, так как их совместимость зависит от совместимости пары 2, 1 (что имеет место в данном примере). Пара состояний 2, 3 также является условно совместимой, так как их совместимость зависит от совместимости пар 2, 4 и 1, 3. Несовместимыми являются пары 1, 4 и 1, 3, поскольку для них не выполняется условие совместимости по выходам.

Для определения множеств совместимых состояний минимизируемого автомата можно пользоваться специальной треугольной таблицей, строки и столбцы которой соответствуют внутренним состояниям автомата. Столбцы обозначаются слева направо номерами состояний 1, 2, ..., z–1. Строки нумеруются сверху вниз номерами состояний 2, 3, …, z. Каждой паре состояний соответствует одна клетка. В клетке ставится символ «X», если данная пара состояний несовместима по выходам. Совместимым парам состояний соответствуют клетки с символом «V». Если совместимость рассматриваемой пары состояний зависит от совместимости других пар, то последние записываются в эту клетку.

После занесения в треугольную таблицу информации о каждой паре состояний необходимо все пары условно совместимых состояний перевести либо в разряд несовместимых, либо в разряд совместимых. Если условная совместимость пары зависит от пары, являющейся несовместимой, или в свою очередь являющейся условно совместимой, зависящей от несовместимой пары, то эта условно совместимая пара переводится в разряд несовместимых. Если на совместимость условно совместимой пары не влияют несовместимые пары состояний, то это пара является совместимой. Окончательный вид треугольной таблицы, где все пары являются совместимыми или несовместимыми, будем называть картой финальных пар (КФП).

Дальнейшая минимизация числа состояний заключается в попытке объединении пар совместимых состояний в более крупные группы, все состояния которых совместимы между собой, и замене каждой группы состояний одним, представляющим в минимальном автомате все состояния группы. Подобные группы состояний будем называть максимально совместимыми множествами (МС-множества).

Рассмотрим подход к формированию МС-множеств на примере. Пусть подлежащий минимизации автомат задан табл. 5.11. Определим для него совместимые пары состояний, которые запишем в треугольную таблицу, соответствующую рассматриваемому автомату (табл. 5.12).

Таблица 5.11

Таблица 5.12

В таблице 5.12 пронумерованы строки и столбцы. В дальнейшем будем использовать совмещенную нумерацию.

Переведем теперь условно совместимые пары состояний в разряд совместимых или в разряд несовместимых пар. Будем полагать, что по умолчанию все условно совместимые пары состояний могут быть совместимыми, если нет информации о том, что для каких-то из них это не так.

Рассмотрим пару состояний 2, 5. Согласно табл. 5.12, совместимость этой пары зависит от совместимости пары 1, 6, которая, как указано в таблице, является несовместимой. Следовательно, рассматриваемая пара состояний 2, 5 также будет являться несовместимой. Вследствие несовместимости 2, 5 также оказывается несовместимой пара 5, 7. Далее отмечаем несовместимость пар состояний 3, 6 и, как следствие, 2, 7. Остальные условно совместимые пары состояний полагаем совместимыми.

Составим отдельной таблицей карту финальных пар (табл. 5.13).

Таблица 5.13

Для нахождения МС-множеств можно воспользоваться следующим подходом.

Сначала для каждого состояния автомата из КФП определяются все пары совместимых состояний, в которые это состояние входит. Каждая пара входит в запись только один раз в столбце таблицы, соответствующем меньшему по номеру состоянию данной пары (табл. 5.14).

Таблица 5.14

Далее проверяется возможность объединения пар в более крупные группы. Поскольку в данном примере столбцы 5, 6, 7 содержат не более одной пары, для них эта возможность не проверяется.

Последовательно рассмотрим интересующие нас столбцы табл. 5.14 слева направо. Объединять пары состояний можно только тогда, когда всевозможные пары состояний получаемой группы являются совместимыми. Для этого необходимо проанализировать содержимое столбцов таблицы, расположенных справа от рассматриваемого: если в этих столбцах имеются все необходимые пары, то объединение пар совместимых состояний в укрупненную группу возможно.

Для рассматриваемого примера искомые МС-множества записаны в табл. 5.14 отдельной строкой снизу.

МС-множества, являющиеся подмножествами других МС-множеств должны быть исключены. Если совокупность МС-множеств не содержит какие-либо состояния исходного автомата, они должны быть добавлены.

Совокупность МС-множеств содержит 6 элементов: С={1, 2; 1, 5; 1, 7; 2, 3, 4; 3, 4, 5; 4, 5, 6}, что соответствует 6 состояниям новой таблицы переходов эквивалентного автомата. Однако нетрудно заметить, что полученная совокупность МС-множеств содержит повторяющиеся состояния, которые необходимо попытаться исключить. Это может привести к уменьшению числа МС-множеств и, как следствие, дальнейшему сокращению числа состояний автомата.

При исключении повторяющихся состояний следует понимать, что, во-первых, исключаемое из какого-либо МС-множества состояние должно остаться в каком-нибудь другом МС-множестве, а во-вторых, в первую очередь необходимо исключать такие повторяющиеся состояния, исключение которых приведет к нарушению совместимости как можно меньшего числа пар состояний.

Нетрудно видеть, что исключение МС-множества (1, 2) из С вполне допустимо, поскольку от совместимости этой пары не зависит совместимость других пар. Если исключить МС-множество (1, 5), согласно табл. 5.12 нарушится совместимость пары 3, 5, вследствие чего МС-множество (3, 4, 5) будет преобразовано к виду (3, 4). Таким образом, С ={1, 7; 2, 3, 4; 3, 4; 4, 5, 6} и МС-множество (3, 4) может быть исключено, поскольку оно является подмножеством (2, 3, 4). В оставшихся МС-множествах повторяется состояние 4, которое может быть исключено из (2, 3, 4), так как от совместимости пар состояний 2, 4 и 3, 4 не зависит совместимость других пар. Однако это не приведет к уменьшению числа МС-множеств, т.е. с точки зрения уменьшения числа состояний эквивалентного автомата исключение состояния 4 не принципиально.

Окончательно, С ={1, 7; 2, 3; 4, 5, 6}.

Для составления таблицы переходов минимального автомата необходимо обозначить полученные МС-множества номерами его состояний. Пусть номерам состояний 1, 2, 3 минимального автомата соответствуют множества состояний исходного автомата (1, 7), (2, 3) и (4, 5, 6). В принципе определение соответствия может быть выполнено произвольно, однако в некоторых случаях может быть удобным, если начальное состояние минимального автомата соответствует МС-множеству, содержащему начальное состояние исходного автомата.

Таблица переходов минимального автомата для рассматриваемого примера имеет следующий вид (табл. 5.15):

Таблица 5.15

В заключение отметим, что рассмотренный подход без изменений может быть применен для минимизации числа состояний автоматов Мура.

5.2.2. Минимизация числа состояний автомата Мура
методом l-эквивалентных разбиений

Вначале дадим несколько определений.

Два состояния автомата Мура называются 0-эквивалентными, если они отмечены одинаковым выходным сигналом.

Совокупности 0-эквивалентных состояний образуют 0-класс.

Если два 0-эквивалентных состояния, принадлежащие к одному классу, любым входным сигналом переводятся также в 0-эквивалентные состояния, то они являются 1-эквивалентными.

Совокупности 1-эквивалентных состояний образуют 1-класс.

Если разбиение на i-классы совпадает с разбиением на (i+1)-классы, то (i+1)-класс называется ¥-классом.

Рассмотрим процесс минимизации на примере. Пусть исходный автомат задан табл. 5.16.

Таблица 5.16

Произведем два последовательных разбиения: на 0-классы (табл. 5.17), а затем на 1-классы (табл. 5.18) и 2-классы (табл. 5.19).

Таблица 5.17

Таблица 5.18

Таблица 5.19

Очевидно, что дальнейшие разбиения будут совпадать с разбиением на 2-классы. Таким образом, в эквивалентном автомате будут шесть состояний, соответствующих разбиению на 2-классы (A – 1, B – 2, C – 3,
D – 4, E – 5, F – 6). В табл. 5.20 представлены переходы и выходные сигналы автомата.

Таблица 5.20

5.2.3. Минимизация числа состояний автомата Мили
методом l-эквивалентных разбиений

Два состояния автомата Мили будут 0-эквивалентными, если находящийся в этих состояниях автомат под воздействием эквивалентных входных сигналов выдает одинаковые выходные сигналы.

Два состояния a_i и a_j автомата Мили будут l‑эквивалентными, если выполняются следующие условия:

1) a_i и a_j (l–1)-эквивалентны;

2) множества классов (l–1)-эквивалентных состояний, в которые осуществляются переходы из a_i и a_j, равны между собой;

3) множества выходных сигналов, формируемых на переходах из a_i и a_j в состояния из некоторого (l–1)-го класса эквивалентности, равны между собой;

4) входные сигналы, приводящие к формированию одинакового выходного сигнала из состояний a_i и a_j, эквивалентны.

Рассмотрим пример.

Представим таблицу переходов исходного автомата Мили в следующем виде (табл. 5.21).

Таблица 5.21

Исходное состояние	Состояние перехода	Входной сигнал	Выходной сигнал	Классы
				B1
				B2
				B2
				B2
				B1
				B3
				B3
				B4
				B4

Из таблицы видно, что произведено разбиение на 4 класса: B1, B2, B3, B4. Для проведения следующего разбиения перепишем эту таблицу в другом виде (табл. 5.22).

Таблица 5.22

Исходное состояние	Состояние перехода	Входной сигнал	Выходной сигнал	Классы
	B2 B2 B2 B1			C1
	B2 B2 B2 B1			C1
	B3 B4 B3 B4			C2
	B3 B3			C3
	B3 B4			C2
	B2 B4			C4
	B2 B4			C4
	B1			C5
	B1			C5

В результате очередного разбиения получены 5 классов: C1, C2, C3, C4, C5. Дальнейшее разбиение невозможно, поэтому сформируем таблицу переходов минимального автомата, имеющего пять внутренних состояний (табл. 5.23).

Таблица 5.23

Исходное состояние	Состояние перехода	Входной сигнал	Выходной сигнал