Трансформация автомата Мили в автомат Мура

 

1 задание: Трансформация автомата Мили в автомат Мура

Исходный автомат Мили представлен  матрицами переходов и выходов.

1) Изобразить граф автомата Мили.

2) Построить граф эквивалентного  автомата Мура.

3) Найти реакции автоматов Мура  и Мили, если на вход автоматов  подается последовательность 

x₁={z₁,z₂,z₂,z₁,z₁,z₁,z₂,z₁,z₂,z₁};

x₂={z₂,z₂,z₁,z₁,z₂,z₂,z₂,z₁,z₁,z₁}.

Исходная таблица переходов  A а a1 a2 a3 a4 a5 a6 z1 а2 а4 a6 а4 a1 a2 z2 a3 a5 a1 a2 a4 a5

Исходная таблица выходов W   a1 a2 a3 a4 a5 a6 z1 w1 w1 w2 w1 w2 w3 z2 w2 w3 w1 w2 w1 w1

Каждому столбцу из приведенных  таблиц поставлено в соответствие одно состояние из множества А, каждой строке - один входной сигнал из множества Z.

Совместим две таблицы в одну: совмещённую таблицу переходов-выходов:

	а1	а2	а3	а4	а5	а6
а1		z1/w1	z2/w2
а2				z1/w1	z2/w3
а3	z2/w1					z1/w2
а4		z2/w2		z1/w1
а5	z1/w2			z2/w1
а6		z1/w3			z2/w1

 

 

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

 

 

Построим  граф эквивалентного автомата Мура.

Два автомата S1 и S2 называются эквивалентными, если:

а) входной и выходной алфавиты совпадают;

б) их реакции из исходного состояния  на любое входное слово совпадают;

Существует теорема: для любого автомата Мура существует эквивалентный  автомат Мили и наоборот.

Построим  множество состояний A_b автомата Мура, для чего найдем множества пар, порождаемых каждым состоянием автомата S_a.

Состояние	Порождаемые пары
А1=	{<a1,w1>, <a1,w2>}={b1,b2}
А2=	{<a2,w1>,<a2,w2>,<a2,w3>}={b3,b4,b5}
А3=	{<a3,w2>}={b6 }
А4=	{<a4,w1>}={ b7 }
А5=	{<a5,w1>,<a5,w3>,}={b8,b9}
А6=	{<a6,w2>}={b10}

Отсюда  имеем множества состояний автомата Мура

A_b={b₁,b₂,b₃,b₄,b₅,b₆,b₇,b₈,b₉,b₁₀}.

Построим  граф эквивалентного автомата Мура

 

 

 

 

 

 

 

 

Найдем реакции автоматов Мура и Мили, если на вход автоматов подается последовательность:

 

x₁={z₁,z₂,z₂,z₁,z₁,z₁,z₂,z₁,z₂,z₁}

реакция автомата Мили: w₁, w₃, w₁, w₁, w₁, w₁, w₂, w₁, w₂, w₁.

реакция автомата Мура:w₁, w₃, w₁, w₁, w₁, w₁, w₂, w₁, w₂, w₁.

x₂={z₂,z₂,z₁,z₁,z₂,z₂,z₂,z₁,z₁,z₁}

реакция автомата Мили: w₂, w₁, w₁, w₁, w₂, w₃, w₁, w₁, w₁.

реакция автомата Мура: w₂, w₁, w₁, w₁, w₂, w₃, w₁, w₁, w₁.

Эквивалентность доказана.

 

 

2 задание: Построение автомата Мура по ГСА

1. По заданной ЛСА построить ГСА.
2. Построить граф автомата Мура по ГСА.

Y₀↓¹Y₁Y₂X₁↑¹↓²Y₃↓⁶Y₆X₂↑³Y₅↓⁷Y₄X₄↑²ω↑⁵↓³X₃↑⁶ω↑⁷↓⁵Y_к

 

По заданной ЛСА построим ГСА, соблюдая следующие условия:

• Если x_i=1, то после Y_pвыполнится Y_m ,
• Если x_i=0, то после Y_p выполнится Y_n,
• Безусловный переход в нашем случае обозначен символом ω↑.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Построим  граф автомата Мура по ГСА.

Переход осуществляем два этапа. На первом этапе производим определение числа состояний путем разметки и отметки граф-схемы; на втором - определение графа автомата. Используем следующие правила разметки:

• Символом а₁ помечаем начальную и конечную вершины ГСА микропрограммы.
• Символами а₂, а₃, а₄, а₅, а₆, а₇ помечаем операторные вершины.
• Разные вершины ГСА должны отмечаем разными метками.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

Получаем  следующий граф абстрактного автомата Мура:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 задание: Построение автомата Мили по ГСА

	Y1	Y2	Y3	Y4	Y5	Y6	Y7	Y8	Y9	Yк
Y0	1	Р1
Y1			2	Р2
Y2					1
Y3					1
Y4						1
Y5					3	Р3
Y6							1
Y7								1
Y8				4					Р4
Y9										1

1. По матричной схеме алгоритма построить ГСА.
2. По ГСА записать ЛСА.
3. По ГСА построить автомат Мили.

По матричной схеме

 алгоритма  построим ГСА.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

По ГСА запишем ЛСА.

Y₀p₁↑¹Y₂↓⁵↓³Y₅p₃↑³ω↑²↓¹Y₁p₂↑⁴↓⁶Y₄↓²Y₆Y₇Y₈p₄↑⁶Y₉ω↑⁷↓⁴Y₃ω↑⁵↓⁷Yk

По ГСА построим автомат  Мили. Переход осуществляем в два этапа. На первом этапе производим определение числа состояний путем разметки и отметки граф-схемы; на втором - определение графа автомата. Используем правила разметки:

• Символом а₁помечаем вход вершины следующей за начальным оператором в ГСА и вход конечной вершины.
• Символами а₂, а₃, а₄, а₅, а₆, а₇, а₈, а₉, а₁₀- входы вершин, следующих за операторными вершинами.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Переход от отмеченных граф-схем к графу автомата осуществляется в следующем порядке:

Вершинами графа изображаются все состояния автомата и внутри кружков записываются символы а₁,а₂, а₃, а₄, а₅, а₆, а₇, а₈, а₉, а₁₀, то есть существующие метки на ГСА.

На  граф-схеме микропрограммы отыскиваем путь между двумя соседними состояниями. Пути отображаются дугами.

На втором этапе строим граф автомата Мили. Имеем десять вершин графа соответствующих десяти состояниям.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Литература

1. Основы алгоритмизации и программирования: уч. пособие / Голицына О.Л.,  Попов И.И. -  М.: ФОРУМ-ИНФРА-М, 2007. – 432 с.
2. Новиков Ф.А. Дискретная математика для программистов.

Сайты:

3. http://www.intuit.ru