Синтез автомата Мілі по ГСА

На етапі отримання розміченої ГСА входи вершин, що йдуть за операторними, відмічають символами q₀, q₁,… за наступними правилами:

1) символом q₀ відмічають вхід вершини, що йде за початковою, а також вхід кінцевої вершини;

2) входи усіх вершин що йдуть за операторними, мають бути відмічені;

3) входи різних вершин, за винятком кінцевої, відзначаються різними символами;

4) вхід вершини відзначається, то тільки одним символом.

Для проведення відміток буде потрібно кінцеве число символів q₀, q₁.., q _m. Результатом першого етапу є розмічена ГСА, яка служить основою для другого етапу - переходу до графа або таблиць переходів-виходів. Приклад ГСА, розміченої для автомата Мілі, представлений на рис. 2.19.

На іншому етапі з відміченої ГСА будують граф автомата або таблиці переходів - виходів. Для цього вважають, що в автоматі буде стільки станів, скільки символів q_i знадобилося при відмітці ГСА.

Для кожного із станів q_i визначаємо по відміченій ГСА усі шляхи, що ведуть в інші стани і проходять обов'язково тільки через одну операторну вершину. Наприклад, із стану q₀ (рис.7.3) є перехід в стан q₁ (шлях проходить через операторну вершину y₁ y₂) і в стан q₃ (шлях проходить через вершину y₃ y₄). Переходу з q₀ в q₂ немає, оскільки на цьому шляху немає жодної операторної вершини. Вважатимемо, що автомат здійснює перехід, наприклад, з q₀ в q₁ за умови x₁ = 0 або і формує на цьому переході вихідні сигнали у₁у₂ (те, що записано в прохідній операторній вершині ГСА). Значення умов х₂, х₃, х₄ на цьому переході не чинить впливу на автомат. Виключення складає тільки шлях, що веде в кінцеву вершину, він може не містити жодної операторної вершини (наприклад, перехід з q₅ в q₀), тобто не супроводжується формуванням вихідних сигналів.

Рисунок 2.19 - ГСА для автомата Мілі

Відмічаємо на графі усі вказані шляхи для усіх станів у вигляді дуг, яким приписуємо умови переходу і вихідного сигналу, що виробляється на цьому переході. Отримаємо граф автомата Мілі (рисунок 2.20).

На цьому графові переходам типу q₂ →q₃, q₄ → q₀ приписується умова переходу 1, оскільки ці переходи є безумовними і виконуються завжди, коли автомат потрапляє в стан q₂ або q₄. На підставі відміченої ГСА або графа автомата можна побудувати таблицю переходів-виходів. Для мікропрограмних автоматів таблиця переходів-виходів будується у вигляді списку, і розрізняється пряма та зворотна таблиці.

Для цього автомата пряма таблиця представлена в таблиці 2.12, зворотна - в таблиці 2.13.

Рисунок 2.20 - Граф автомата Мілі

Таблиця 2.12 - Пряма таблиця переходів-виходів автомата Мілі

qm	qs	X	Y
q0	q1 q3	x1	y1y2 y3y4
q1	q1 q4 q5	x3 x3x2	y1y2 y2y3 y4
q2	q3		y3y4
q3	q0 q2	x2	y2 y1y4
q4	q0		y2
q5	q0 q1	x4	- y1y2

Таблиця 2.13 - Зворотна таблиця переходів-виходів автомата Мілі

qm	qs	X	Y
q3 q4 q5	q0	x4	y2 y2 -
q0 q1 q5	q1	x1	y1y2 y1y2 y1y2
q3	q2	x2	y1y4
q0 q2	q3	x1 1	y3y4 y3y4
q1	q4		y2y3
q1	q5	x3x2	y4

У приведених таблицях q_m - початковий стан, q_s - стан переходу, Х - умова (вхідний сигнал), перехід, що забезпечує, із стану q_m в стан q_s, Y - вихідний сигнал, що виробляється автоматом при переході з q_m в q_s.