1. 2.3 Перетворення автоматів Мура в еквівалентні автомати Мілі При табличному завданні таблиця переходів...

2.3 Перетворення автоматів Мура в еквівалентні автомати Мілі

При табличному завданні таблиця переходів автомата Мілі збігається з таблицею переходів автомата Мура. Таблиця виходів автомата Мілі виходить з таблиці переходів заміною символу , Що стоїть на перетині рядка і стовпці , На символ , Що відзначає стовпець в суміщеної таблиці автомата Мура.

Нехай заданий автомат Мура ( табл.2.4 ). Таблиця переходів еквівалентного автомата Милі ( табл.2.5 ) Збігається з поєднаною таблицею автомата Мура, що представляє переходи автомата, а таблиця виходів 2.6 отримана в такий спосіб. Вважається, що на переході зі стану в стан в еквівалентному автоматі Мілі повинен бути сформований такий же вихідний сигнал, що і в автоматі Мура, після того як автомат перейшов в стан , Тобто вихідний сигнал .

Таблиця 2.4. w1 w2 w3 w2 w3 a1 a2 a3 a4 a5 z1 a2 a5 a5 a3 a3 z2 a4 a2 a2 a1 a1 Таблиця 2.5. a1 a2 a3 a4 a5 z1 a2 a5 a5 a3 a3 z2 a4 a2 a2 a1 a1 Таблиця 2.6. a1 a2 a3 a4 a5 z1 w2 w3 w3 w3 w3 z2 w2 w2 w2 w1 w1

Розглянемо перехід автомата зі стану в стан . В автоматі Мура станом відповідає вихідний сигнал , Отже в табл.2.6 на переході зі стану по вхідному сигналу ставимо і так далі.

При графічному завданні автомата Мура перехід до автомату Мілі виконується наступним чином: вихідний сигнал , Що формується в стані , Переноситься на все дуги, що входять в цю вершину, графічна інтерпретація цього показана на рис.2.4 , А приклад трансформації автомата Мура в еквівалентний автомат Мілі показаний на рис.2.5 .

2.4 Перетворення автоматів Мілі в еквівалентні автомати Мура

Обмеження: В автоматі Мілі не повинно бути переходять станів, тобто станів, в яких є хоча б одна виходить дуга і немає жодної входить дуги, так як показано на рис.2.6 .

В автоматі Мура вихідний сигнал формується як функція , А в автоматі Мілі - . причому - поточний стан автомата, - попередній стан автомата. Таким чином, стан відповідає групі , Число яких дорівнює кількості різних вихідних сигналів , Розташованих на вхідних дугах. Графічна інтерпретація цього показана на рис.2.7 .

Нехай дано автомат Мілі: . Потрібно перейти до еквівалентного автомата Мура , Тобто потрібно побудувати такий автомат Мура: , що і . Розглянемо приклад. Дан автомат Мілі ріс.2.8-2.9 . Побудуємо безліч станів автомата . Для цього знаходимо пари:

;

;

;

.

переобозначив відповідно як , Отримаємо граф, зображений на ріс.2.8-2.9 .