Автомат Мура - модель управляющего автомата

Для формирования автоматной модели необходимо:

1) все блоки "оператор" пометить символами y_i и q_i; управляющий автомат по сигналу “1” формирует команду для операционного автомата на исполнение y_i-ой операции и одновременно переходит в q_i-е состояние; операционный автомат после исполнения команды формирует сигнал "1" для управляющего автомата;

2) все блоки "предикат" пометить символами p_i; операционный автомат проверяет p_i -ое условие и формирует сигналы “p” или “`p” для управляющего автомата;

3) блок "начало" пометить символом q₀; управляющий автомат до команды “старт” (символ "1") находится в состоянии q₀;

4) блок "конец" пометить символом q_k=q₀ (управляющий автомат переводится в начальное состояние); после исполнения алгоритма на управляющий автомат подается команда “стоп” (символ "0").

Пусть даны блок-схемы некоторых алгоритмов (см. рис.6.11).

Разметка блок-схемы согласно правилам позволяет выделить множества входных и выходных сигналов управляющего автомата и его внутренние состояния:

a) X={0;1;p;p-}; Y={0; y₁}; Q={q₀;q₁};

b) X={0;1;p;p-}; Y={0; y₁; y₂}; Q={q₀;q₁;q₂};

c) X={0;1;p-₁;p₁.p₂;p₁.p-₂}; Y={0;y₁}; Q={q₀;q₁};

d) X={0;1;p₁;p-₁.p₂;p-₁.p-₂}; Y={0;y₁; y₂}; Q={q₀;q₁;q₂}.

Поведения автоматов Мура, реализующих управление алгоритмами, приведены в таблице 6.13.

 

Таблица 6.13

a)

b)

текущее состояние (выход)

входные символы

текущее состояние (выход)

входные символы

p

p-

p

p-

q0(0)

q1

—

—

q0(0)

—

q1

q2

q1(y1)

—

q0

q1

q1(y1)

q0

—

—

q2(y2)

q0

—

—

c)

d)

текущее состояние (выход)

входные символы

текущее состояние (выход)

входные символы

p-1

p1.p2

p1.p-2

p1

p-1.p2

p-1.p-2

q0(0)

q1

—

—

—

q0(0)

—

q1

q2

q0

q1(y1)

—

q1

q0

q1

q1(y1)

q0

—

—

—

q2(y2)

q0

—

—

—

Пример: на рис. 6.12. дана блок-схема алгоритма. Найти таблицу поведения управляющего автомата Мура.

Разметка блок-схемы согласно правилам позволяет выделить множества входных сигналов для управляющего автомата и его внутренние состояния:

X={0;1; p-; p₁.p₂; p₁.p-₂; (p₃.p₄Úp-₃.p₅); (p₃.p-₄Úp-₃.p-₅)};

Q={q₀; q₁; q₂; q₃; q₄}.

Введем обозначения k₁=(p₃.p₄Úp-₃.p₅), k₂=(p₃.p-₄Úp-₃.p-₅).

На входе оператора 2 действуют также два сигнала: от выхода оператора 1 сигнал (p₁×p₂) и от выхода оператора 3 - (p₃.p-₄ Ú p-₃.p-₅). Переход в заключительное состояние также из двух состояний: от оператора 4 по сигналу “1” и от оператора 3 по сигналу (p₃.p-₄ Ú p-₃.p-₅). Введем обозначения k₁=(p₃.p₄ Ú p-₃.p₅), k₂=(p₃.p-₄ Ú p-₃.p-₅).

Поведение управляющего автомата Мура представлено в таблице 6.14.

Таблица 6.14

текущие состояния (выход)	входные символы
	p-1	p1.p2	p1.p-2	k1	k2
q0 (0)	q1	—	—	—	—	—
q1 (y1)	—	q1	q2	q4	—	—
q2 (y2)	q3	—	—	—	—	—
q3 (y3)	—	—	—	—	q0	q2
q4 (y4)	q0	—	—	—	—	—

Микропрограммный автомат

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

Элементарная операция, выполняемая операционным автоматом за один шаг и приводимая в действие одним управляющим сигналом от управляющего автомата, называется микрооперацией.

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

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

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

Такты	Операторы и условия	Комментарии
	y1: РгВ:=ШиВх	принять во входной регистр сумматора В первый операнд из входной шины ШиВх;
	y2: Рг1:=ШиВх	принять в регистр 1 АЛУ второй операнд из входной шины ШиВх;
	условие	второй операнд положительный?
	p1	"да",
	p-1	"нет";
	y3: РгА:=Pг1	если второй операнд положительный, то принять во входной регистр сумматора А второй операнд из Рг1 в прямом коде;
	y4: РгА=-Рг1	если второй операнд отрицательный, то принять во входной регистр сумматора А второй операнд из Рг1 в обратном коде;
	условие	операция сложения?
	p2	"да",
	p-2	"нет";
	y5: РгСм:=РгА+РгВ	если p2, то принять в выходной регистр сумматора См значение cуммы двух операндов;
	y6:: РгСм:=РгА+РгВ+1	Если не p2, то` принять в выходной регистр сумматора См значение суммы двух операндов и прибавить "+1";
	y7: ШиВых:=РгСм	Выдать в шину выхода ШиВых значения выходного регистра РгСм сумматора.

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

Таблица 6.15

qÎQ	символы входного алфавита xÎX
	p1	p-1	p2	p-2
q0	q1; y1	—	—	—	—
q1	q2; y2	—	—	—	—
q2	—	q3; y3	q4; y4	—	—
q3	—	—	—	q5; y5	q6; y6
q4	—	—	—	q5; y5	q6; y6
q5	q7; y7	—	—	—	—
q6	q7; y7	—	—	—	—
q7	q0; -	—	—	—	—

В таблице 6.15 дано описание автомата Мили на основе выполненной разметки блок-схемы алгоритма.

Эквивалентность автоматов

Эквивалентность автоматов определяют по их реакции на входные последовательности символов, то есть по формированию одинаковых выходных последовательностей.

Так как модель автомата представляет трехосновную алгебру, то для сравнения двух автоматов необходимо найти три оператора, формирующих отображение множеств X, Q и Y одного автомата на соответствующие множества другого автомата. После этого необходимо оценить влияние этих операторов на исполнение функций переходов и выходов каждым автоматом.

Рассмотрим модели двух абстрактных автоматов:

Пусть даны операторы:

Если при исполнении функций переходов и выходов выполняются условия

 

то совокупность операторов J=<f; g; h> определяет гомоморфное отображение автомата М₁ на автомат М₂ когда каждому значению x_1kÎX₁, y_1jÎY₁ и q_1iÎQ₁ соответствуют единственные образы x_2kÎX₂, y_2jÎY_2,, q_2iÎQ₂.

Пусть даны операторы:

Если при исполнении функций переходов и выходов выполняются условия:

то совокупность операторов J^-1=<f^-1;g^-1;h^-1> определяет гомоморфное отображение автомата М₂ на автомат М₁ .

Если найдены операторы J и J^-1, для которой

J×J^-1 =1,

то такое взаимное отображение называют изоморфным.

Изоморфное отображение рефлексивно, симметрично и транзитивно.

Особый интерес для оценки эквивалентности автоматов представляет случай, когда f =1, т. е. X₁=X₂=X. Тогда для x_kÎX имеем:

Если существуют такие q_1i и q_2i, для которых значения функций выходов j₁(q_1i; x_k) и j₂₍q_2i; x_k) совпадают для всех x_kÎX, то есть

 

j₁(q_1i; x_k)=j₂(q_2i; x_k),

то g=g^-1=1. При этом Y₁=Y ₂ =Y. Такие состояния q_1i и q_2i называют неотличимыми по выходу автоматов.

В результате просмотра множества пар неотличимых состояний (q_1i; q_2i)Î(Q₁ÄQ₂) можно найти несколько подмножеств, которые формируют разбиение множества {(q_1i; q_2i)}Í(Q₁ÄQ₂) на классы неотличимых состояний.

Если для пары неотличимых состояний (q_1i; q_2i) значения функций переходов формируют для всех символов x_kÎX также пары неотличимых состояний (y(q_1i[t]; x_k[t]); y(q_2i[t]; x_k[t]))Î (Q₁ÄQ₂), то состояния q_1i и q_2i называют совместимыми.

В результате просмотра {(y(q_1i[t]; x_k[t]); y(q_2i[t]; x_k[t]))}Í (Q₁ÄQ₂) всех пар одного класса неотличимых состояний формируется разбиение этого класса на классы совместимых состояний.

Состояния q_1i и q_2i являются эквивалентными, если для всякой входной последовательности a=(x₁x₂...x_n) выполняется условие:

М₁(q_1i; a)=М₂(q_2i; a).

Поэтому необходимо проследить изменения значений функций переходов (y(q_1i[t]; x_k[t]); t(q_2i[t]; x_k[t])) для каждого символа входной последовательности a=(x₁x₂...x_n).

Множество всех пар (q_1i; q_2i), для которых выполняется условие М₁(q_1i; a)=М₂(q_2i; a) формирует класс эквивалентных состояний.

Если входной и выходной алфавиты у двух автоматов совпадают, то автомат M₂ покрывает автомат M₁, если j₂(h(q_1i); a)=j₁(q_1i; a) для всех aÎXⁿ, а автомат M₁ покрывает автомат M₂, если входной и выходной алфавиты у этих автоматов общие и j₁(h^-1(q_2i); a)=j₂(q_2i; a) для всех aÎXⁿ.

По условиям изоморфизма автоматы M₁ и M₂ эквивалентны, если M₁ покрывает M₂ и M₂ покрывает M₁. У эквивалентных автоматов существуют эквивалентные состояния q_1i и q_2i.

Если для эквивалентных автоматов М₁ и М₂ |Q₁|<|Q₂|, то автомат М₁, имеющий меньшее число состояний, покрывает автомат М₂, имеющий большее число состояний. Автомат, который нельзя покрыть автоматом с меньшим числом состояний, называют минимальным.

Для поиска эквивалентных состояний q_1i и q_2i удобно использовать таблицы переходов пар состояний двух автоматов. В каждой паре левый элемент есть состояние автомата М₁, а правый - состояние автомата М₂. Левый столбец такой таблицы предназначен для указания неотличимых пар состояний, которые формируются по таблицам выходов автоматов, руководствуясь следующим правилом:

"если среди множества состояний двух автоматов Q₁ и Q₂ найдется такая пара (q₁;q₂), у которой значения функций выходов равны для каждого символа входного алфавита, т.е. j₁(q_1i; x_k)=j₂(q_2i; x_k), то состояния q₁ и q₂ неотличимы;"

Позициями таблицы являются пары состояний двух автоматов, в которые они переходят из соответствующих пар неотличимых состояний при подаче на входы автоматов символа x_k. Значения очередных состояний могут быть найдены по таблицам переходов автоматов М₁ и М₂ для соответствующего символа x_kÎX.

Пусть таблица переходов пар состояний двух автоматов представлена таблицей 6.16, где пары неотличимых состояний, приведенные в левом столбце.

Таблица 6.16.

неотличимые состояния (q1;q2)	xiÎX
x1	x2	…	xn
…	…	…	…	…
(q1i;q2j)	(q1i;q2j)	(q1j;q2p)	…	(q1s;q2i)
(q1j;q2p)	(q1i;q2j)	(q1p;q2p)	…	(q1s;q2i)
(q1p;q2s)	(q1j;q2p)	(q1j;q2p)	…	(q1j;q2p)
(q1s;q2i)	(q1s;q2p)	(q1p;q2j)	…	(q1j;q2i)

Анализ таблицы показывает, что

· состояния q_1i и q_2j совместимы, т.к. при приеме каждого символа входного алфавита неотличимые состояния автоматов М₁ и М₂ переходят в в пары также неотличимых состояний;

· состояния q_1p и q_2s совместимы, т.к. при приеме каждого символа входного алфавита неотличимые состояния автоматов М₁ и М₂ остаются в одной паре неотличимых состояний;

· состояния q_1j и q_2p несовместимы, т.к. при приеме символа x₂ неотличимые состояния автоматов М₁ и М₂ переходят в различные пары неотличимых состояний;

· состояния q_1s и q_2i несовместимы, т.к. при приеме каждого символа входного алфавита неотличимые состояния автоматов М₁ и М₂ переходят в различные пары неотличимых состояний.

Следовательно, автоматы М₁ и М₂, даже при наличии совместимых состояний, не эквивалентны между собой.

 

Пример: даны автомат M₁=<X₁; Y₁; Q₁; y₁; j₁,>, где X₁={0;1}, Y₁={0; 1}, Q₁={q₁₁; q₁₂; q₁₃}, y₁ и j₁ (см. таблицу a)) и автомат M₂=< X₂; Y₂; Q₂; y₂, j₂>, где X₂={0;1}, Y₂={0;1}, Q₂={q₂₁; q₂₂}, y₂ и j₂ (см. таблицу b)). Определить эквивалентность автоматов М₁ и М₂.

Таблица a). Таблица b).

qÎQ1	xÎX1		qÎQ2	xÎX2
q11	q13; 0	q12; 1		q21	q21; 0	q22; 1
q12	q11; 1	q13; 0		q22	q21; 1	q21; 0
q13	q11; 0	q12; 1

 

Для автоматов М₁ и М₂ неотличимыми по выходу являются пары состояний (q₁₁; q₂₁), (q₁₂; q₂₂) и (q₁₃; q₂₁). При этом формируются два класса неотличимых состояний {(q₁₁;q₂₁);(q₁₃;q₂₁)} и {(q₁₂; q₂₂)}.

Если для неотличимой пары (q₁₁;q₂₁) при входном символе "0" автоматы М₁ и М₂ переходят в неотличимую пару состояний (q₁₃;q₂₁), а при входном символе "1" - в неотличимую пару (q₁₂;q₂₂), то состояние q₁₁ автомата М₁ и состояние q₂₁ автомата М₂ являются совместимыми.

Если для неотличимой пары состояний (q₁₂; q₂₂) при входном символе "0" автоматы М₁ и М₂ переходят в неотличимую пару состояний (q₁₁; q₂₁), а при входном символе "1" - в неотличимую пару (q₁₃; q₂₁₎, то состояние q₁₂ автомата М₁ и состояние q₂₂ автомата М₂ также являются совмеcтимыми.

И наконец, если для неотличимой пары состояний (q₁₃; q₂₁) при входном символе "0" автоматы М₁ и М₂ переходят в неотличимую пару состояний (q₁₁; q₂₁), а при входном символе "1" - в неотличимую пару (q₁₂; q₂₂), то состояние q₁₃ автомата М₁ и состояние q₂₁ автомата М₂ являются совместимыми.

Если состояние q₁₃ автомата М₁ совместимо с состоянием q₂₁ автомата М₂, а состояние q₂₁ автомата М₂ совместимо с состоянием q₁₁ автомата М₁, то согласно свойству транзитивности состояние q₁₁ автомата М₁ совместимо с состоянием q₁₃ автомата М₁. Проверку эквивалентности следует проверять по условию М₁(q_1i; a)=М₂(q_2i; a).

Пусть для автомата М₁ имеем q₁₁=q0 и a=(01010101). Тогда процесс обработки входного слова формирует следующие последовательности:

вход: 0[1] 1[2] 0[3] 1[4] 0[5] [6] 0[7] 1[8];

q: q₁₁[1] q₁₃[2] q₁₂[3] q₁₁[4] q₁₂[5] q₁₁[6] q₁₂[7] q₁₃[8] q₁₂[9];

выход: 0[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8],

то есть b₁= (01111111).

 

Пусть для автомата М₂ имеем q₂₁=q₀ и a=(01010101). Тогда процесс обработки входного слова формирует следующие последовательности:

 

вход: 0[1] 1[2] 0[3] 1[4] 0[5] 1[6] 0[7] 1[8];

q: q₂₁[1] q₂₁[2] q₂₂[3] q₂₁[4] q₂₂[5] q₂₁[6] q₂₂[7] q₂₁[8] q₂₂[9];

выход: 0[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8],

то есть b₂=(01111111).

 

Итак, автоматы М₁ и М₂ эквивалентны. Так как автомат М₂ имеет меньшее число внутренних состояний, то он покрывает автомат М₁.

⇐ Предыдущая24252627282930313233Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: