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

Для всякого кінцевого автомата Мілі існує еквівалентний йому (що індукує те ж саме відображення) кінцевий автомат Мура. Існує єдиний конструктивний прийом (універсальний алгоритм перетворення автоматів Мілі в автомати Мура), що дозволяє по довільному кінцевому автомату Мілі, що має m вхідних сигналів і n станів, побудувати еквівалентний йому автомат Мура, що має не більше m⋅n + 1 станів.

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

Рисунок 1. 12 – Перехідний стан автомата Мілі

У автоматі Мура вихідний сигнал формується як функція стану, а в автоматі Мілі - як функція переходу. Таким чином, стан еквівалентного автомата Мура відповідає групі дуг автомата Мілі, число яких дорівнює кількості різних вихідних сигналів, розташованих на дугах, що входять (рис 1.13).

Рисунок 1. 13 – Формування стану еквівалентного автомата Мура

Послідовність переходу наступна

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

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

3. Будується таблиця переходів автомата Мура, яка заповнюється таким чином. Кожен стан b_ij відзначається вихідним сигналом, записаним в комірку автомата Мілі на перетині i -го рядка і j -го стовпця. Наступними для станів автомата Мура будуть стани з проміжної таблиці, записані в стовпці з номером a_k, де a_k - стан автомата Мілі, записаний в таблиці переходів автомата Мілі в комірку на перетині i -го рядка і j -го стовпця.

4. Наступними станами для b₀ будуть наступні стани для початкового стану автомата Мілі в проміжній таблиці. Стан b₀ відзначається таким вихідним сигналом, щоб стовпець b₀ співпав з яким-небудь іншим стовпцем таблиці переходів автомата Мура.

Приклад. Заданий автомат Мілі у вигляді графа (рис. 1.14). Побудувати поєднану таблицю переходів/виходів. Знайти еквівалентний йому автомат Мура, побудувати граф та відмічену таблицю переходів.

Рисунок 1.14 - Граф заданого автомата А₅

Розв’язання завдання.

Поєднана таблиця переходів/виходів має вигляд:

Таблиця 1. 14 - Поєднана таблиця переходів/виходів

	q0	q1	q2	q3
x1	q1 y1	q0 y2	q1 y1	q0 y1
x2	q2 y2	q2 y2	q3 y1	q1 y2

Знаходження еквівалентного автомата Мура.

1. Визначення в таблиці однакових переходів/виходів і позначка їх.

Таблиця 1. 15- Поєднана таблиця визначення однакових переходів/виходів

	q0	q1	q2	q3
x1	q1 y1	q0 y2	q1 y1	q0 y1
s3	s2	s3	s1
x2	q2 y2	q2 y2	q3 y1	q1 y2
s5	s5	s6	s4

Позначка починається з аналізу стану q₀ і вихідної реакції y₁. Якщо така комбінація q₀/y₁ зустрічається в таблиці, то їй приписується позначка s₁. Якщо дана комбінація зустрічається кілька разів, то усім приписується однакова позначка. Далі аналізується наявність комбінації q₀ /y₂, якщо вона зустрічається, то їй приписується позначка s₂, і так далі розглядається наявність усіх комбінацій <стан>/<буква вих. алфавіту> і усім приписуються позначки.

2. Запис множини еквівалентних станів

Кожному початковому стану приписується множина відповідних ним позначок (розглядається побудована таблиця з позначками). Шукається в таблиці черговий початковий стан і у відповідну множину записується приписана йому позначка. Для початкового стану q₀ в множині позначок додається також s₀ - для ідентифікації початкового стану автомата Мура.

Для даного прикладу отримана наступна множина еквівалентних станів.

3. Побудова відміченої таблиці переходів автомата Мура.

Таблиця 1. 16 - Відмічена таблиця переходів

	-	у2	у1	у1	у2	у2	у1
	s0	s1	s2	s3	s4	s5	s6
x1	s3	s3	s3	s2	s2	s3	s1
x2	s5	s5	s5	s5	s5	s6	s4

Загальна кількість станів шуканого еквівалентного автомата Мура дорівнює сумарній кількості проставлених позначок та мітки початкового стану q₀, тобто сумі кількості елементів усіх побудованих еквівалентних множин. В даному випадку множина станів автомата Мура буде наступною: ..

Вихідні реакції записуються таким чином: в таблиці з позначками шукається позначка, відповідна даному стану автомата Мура і у відмічену таблицю автомата Мура записується вихідна реакція, що знаходиться в знайденому осередку.

Запис переходів: розглядається множина еквівалентних станів і в стовпці таблиці автомата Мура, відповідні елементам даної множини, записуються проставлені позначки із стовпця відповідного еквівалентного стану автомата Мілі, наприклад, в стовпці станів s₀, s₁, s₂ автомата Мура будуть записані позначки s₃, s₅ із стовпця q₀ таблиці автомата Мілі.

4. По побудованій відміченій таблиці переходів автомата Мура можна побудувати граф автомата Мура, еквівалентний заданому автомату Мілі (рис. 1.15).

Рисунок 1.15 - Граф автомата Мура, еквівалентного заданому автомату Мілі

Якщо d_p1 і l_к функції переходів та виходів автомата Мура, то функції переходів d_p2(Q, X) і виходів l₂(Q, X) еквівалентного ав­томата Мілі:

d_p2(Q, X) = d_p1(Q, X;

l₂(Q, X) = l₁(d_p1(Q, X))

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

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

Послідовність переходу від моделі Мура до моделі Мілі,наступна:

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

2. Вихідний сигнал автомата Мілі, що формується при переході в стан a_i, співпадає з вихідним сигналом, яким відмічений стан a_i в автоматі Мура.

При такому перетворенні граф автомата Мілі відрізняється від графа автомата Мура лише тим, що вихідні сигнали з вузлів гра­фа перенесені на всі гілки, що входять до цього вузла (рис. 1.16).

Рисунок 1.16 – Перетворення графа автомата Мура

в еквівалентний граф автомата Мілі

Приклад. Заданий автоматМура у вигляді графа (1.17). Знайти еквівалентний йому автомат Мілі, побудувати граф і поєднану таблицю переходів/виходів.

Рисунок 1.17 - Граф заданого автомата

Розв’язання завдання.

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

Рисунок 1.18 - Граф автомата Мілі, еквівалентного заданому автомату Мура

Методи взаємної транспозиції автоматів Мілі і Мура показують, що при переході від автомата Мура до автомата Мілі число станів принципово не міняється. Тоді як при зворотному переході в автомат Мура число станів, як правило, збільшується. Внаслідок транзитивності відношення еквівалентності два автомати Мілі, перший з яких отриманий з автомата Мура, так само будуть еквівалентні, але у другого автомата число станів буде більше. Таким чином еквівалентні між собою автомати можуть мати різне число станів. У зв'язку з чим і виникає завдання знаходження мінімального автомата в класі еквівалентних між собою автоматів. Існування для будь-якого абстрактного автомата еквівалентного йому абстрактного автомата з мінімальним числом внутрішніх станів уперше було доведене Муром.