Мінімізація числа станів синхронного автомата методом Пола-Ангера

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

Сукупність станів таблиці переходів, що представляються станом якої-небудь іншої таблиці переходів, називатимемо сумісною множиною або множиною сумісних станів. Завдання мінімізації полягає в знаходженні множини сумісних станів з наступною заміною кожної з множин одним станом.

Розглянемо умови, яким повинні задовольняти сумісні стани.

Перша умова сумісності - формування несуперечливих вихідних сигналів при однаковій вхідній змінній. Це означає, що в тих рядках, де вихідні сигнали визначені, вони повинні співпадати.

Приклад. У таблиці стани q₁ і q₂ є сумісними по виходах. Також сумісними по виходах є пари станів q₂, q₃; q₂, q₄; q₃, q₄.

Таблиця 1.19 Таблиця переходів автомата

x \ q	q 1	q 2	q 3	q 4
x 1	q 2 y 1	q 2 y 1	q 4 y 1	q 1 y 1
x 2	– –	q 3 y 1	q 3 y 1	q 3 –
x 3	q 4 y 0	q 4 –	– y 1	q 4 y 1
x 4	q 1 y 1	q 1 y 1	q 3 y 1	– y 1

Друга умова сумісності станів полягає в тому, що переходи з цих станів під впливом однакового вхідного сигналу повинні здійснюватися в однакові стани, якщо обоє вони визначені. Пара станів q ₁, q ₂ задовольняє цій умові, оскільки під впливом усіх вхідних сигналів здійснюються переходи в однакові стани. Пара станів q ₂, q ₄ не задовольняє другій умові сумісності, оскільки під впливом вхідного сигналу х₁ автомат переходить із станів q ₂, q ₄ в стани q ₂, q ₁.

Пари станів, подібні q ₂, q ₄, називаються умовно сумісними, оскільки їх сумісність залежить від сумісності пари q ₂, q ₁ (що має місце в цьому прикладі). Пара станів q ₂, q ₃ також є умовно сумісною, оскільки їх сумісність залежить від сумісності пар q ₂, q ₄ і q ₁, q ₃. Несумісними є пари q ₁, q ₄ і q ₁, q ₃, оскільки для них не виконується умова сумісності по виходах.

Для визначення множини сумісних станів автомата, що мінімізується, можна користуватися спеціальною трикутною таблицею, рядки і стовпці якої відповідають внутрішнім станам автомата. Стовпці позначаються зліва направо номерами станів q ₁, q ₂,.., q _{z - 1}. Рядки нумеруються зверху вниз номерами станів 2, 3,., z. Кожній парі станів відповідає одна клітина. У клітині ставиться символ "X", якщо ця пара станів несумісна по виходах. Сумісним парам станів відповідають клітини з символом "V". Якщо сумісність даної пари станів залежить від сумісності інших пар, то останні записуються в цю клітину.

Після занесення в трикутну таблицю інформації про кожну пару станів необхідно усі пари умовно сумісних станів перевести або в розряд несумісних, або в розряд сумісних. Якщо умовна сумісність пари залежить від пари,, що являється несумісною, або що у свою чергу являється умовно сумісною, залежною від несумісної пари, то ця умовно сумісна пара переводиться в розряд несумісних. Якщо на сумісність умовно сумісної пари не впливають несумісні пари станів, то це пара є сумісною. Остаточний вид трикутної таблиці, де усі пари є сумісними або несумісними, називатимемо картою фінальних пар (КФП).

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

Розглянемо підхід до формування МС- множин на прикладі. Нехай що підлягає мінімізації автомат заданий таблиці. 1.20. Визначимо для нього сумісні пари станів, які запишемо в трикутну таблицю, відповідну даному автомату (таблиця. 1.21).

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

x \ q	q 1	q 2	q 3	q 4	q 5	q 6	q 7
x 1	q3 y0	– –	q4 y1	q6 y1	q5 –	q4 y1	q2 y0
x 2	– –	q6 y0	q5 –	– –	q1 –	q7 y1	q3 y0

Таблиця 1.21- Трикутна таблиця автомата

	q 1
	V	q 2
	X	q 5, q 6	q 3
	X	V	q 4, q 6	q 4
	q 3, q 5	q 1, q 6	q 4, q 5 q 1, q 5	q 5, q 6	q 5
	X	X	q 5, q 7	V	q 4, q 5 q 1, q 7	q 6
	q 2, q 3	q 3, q 6	X	X	q 2, q 5 q 1, q 3	Х

У таблиці 1.21 пронумеровані рядки і стовпці. Надалі використовуватимемо поєднану нумерацію.

Переведемо тепер умовно сумісні пари станів в розряд сумісних або в розряд несумісних пар. Вважатимемо, що за умовчанням усі умовно сумісні пари станів можуть бути сумісними, якщо немає інформації про те, що для якихось з них це не так.

Розглянемо пару станів q ₂, q ₅. Згідно таблиці. 1.21, сумісність цієї пари залежить від сумісності пари 1, 6, яка, як вказано в таблиці, є несумісною. Отже, дана пара станів q ₂, q ₅ також буде несумісною. Внаслідок несумісності q ₂, q ₅ також виявляється несумісною пара q ₅, q ₇. Далі відмічаємо несумісність пар станів q ₃, q ₆ і, як наслідок, q ₂, q ₇. Інші умовно сумісні пари станів вважаємо сумісними.

Складемо окремою таблицею карту фінальних пар (таблиця.1.22).

Таблиця 1.22- Карта фінальних пар

q 1
V	q 2
X	V	q 3
X	V	V	q 4
V	X	V	V	q 5
X	X	X	V	V	q 6
V	X	X	X	X	Х	q 7

Для знаходження МС- множин можна скористатися наступним підходом.

Спочатку для кожного стану автомата з КФП визначаються усі пари сумісних станів, в які цей стан входить. Кожна пара входить в запис тільки один раз в стовпці таблиці, відповідному меншому по номеру стану цієї пари (таблиця. 1.23).

Таблиця 1.23 - Таблиця станів автомата

1, 2	2, 3	3, 4	4, 5	5, 6	–	–
1, 5	2, 4	3, 5	4, 6
1, 7
(1, 2), (1, 5), (1, 7)	(2, 3, 4)	(3, 4, 5)	(4, 5, 6)	(5, 6)

Далі перевіряється можливість об'єднання пар в більші групи. Оскільки в цьому прикладі стовпці 5, 6, 7 містять не більше за одну пару, для них ця можливість не перевіряється.

Послідовно розглянемо стовпці таблиці 1.23 зліва направо. Об'єднувати пари станів можна тільки тоді, коли різні пари станів отримуваної групи є сумісними. Для цього необхідно проаналізувати вміст стовпців таблиці, розташованих праворуч від того, що розглядається,: якщо в цих стовпцях є усі необхідні пари, то об'єднання пар сумісних станів в укрупнену групу можливо.

Для даного прикладу шукані МС- множини записані в таблиці 1.23 окремим рядком знизу.

МС- множини, що є підмножинами інших МС- множин мають бути виключені. Якщо сукупність МС- множин не містить які-небудь стани початкового автомата, вони мають бути додані.

Сукупність МС- множин містить 6 елементів: С={1, 2; 1, 5; 1, 7; 2, 3, 4; 3, 4, 5; 4, 5, 6}, що відповідає 6 станам нової таблиці переходів еквівалентного автомата. Проте неважко помітити, що отримана сукупність МС- множин містить стани, що повторюються, які необхідно спробувати виключити. Це може привести до зменшення числа МС- множин і, як наслідок, подальшого скорочення числа станів автомата.

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

Неважко бачити, що виключення МС- множини (1, 2) із С цілком допустимо, оскільки від сумісності цієї пари не залежить сумісність інших пар. Якщо виключити МС- множину (1, 5), згідно таблиці. 1.21 порушиться сумісність пари 3, 5, внаслідок чого МС- множина (3, 4, 5) буде перетворена до виду (3, 4). Таким чином, С ={1, 7; 2, 3, 4; 3, 4; 4, 5, 6} і МС- множина (3, 4) може бути виключена, оскільки вона є підмножиною (2, 3, 4). У МС- множинах, що залишилися, повторюється стан 4, який може бути виключений з (2, 3, 4), оскільки від сумісності пар станів 2, 4 і 3, 4 не залежить сумісність інших пар. Проте це не приведе до зменшення числа МС- множини, тобто з точки зору зменшення числа станів еквівалентного автомата виключення стану 4 не принципово.

Остаточно, С={1, 7; 2, 3; 4, 5, 6}.

Для складання таблиці переходів мінімального автомата необхідно позначити отримані МС- множини номерами його станів. Нехай номерам станів 1, 2, 3 мінімальні автомати відповідають множині станів початкового автомата (1, 7), (2, 3) і (4, 5, 6). В принципі визначення відповідності може бути виконане довільно, проте в деяких випадках може бути зручним, якщо початковий стан мінімального автомата відповідає МС- множині, що містить початковий стан початкового автомата.

Таблиця переходів мінімального автомата для даного прикладу має наступний вигляд (таблиця 1.24):

Таблиця 1.24- Таблиця переходів мінімального автомата

x \ q	q1	q2	q3
x1	q2 y0	q3 y1	q3 y1
x2	q2 y0	q3 y0	q1 y1

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