Мінімізація автомата
Мінімізацією автомата називаємо знаходження еквівалентного автомата, що містить найменшу можливу кількість станів. Навіть автомат, який не містить жодного надлишкового стану, можна ще спростити.
Приклад
Розгляньмо такий автомат:
Автомат допускає лише слова «01» і «11». Очевидно, що існує простіший автомат із трьома станами, який допускає ту саму мову. Стани q1 і q2 можна об'єднати в один новий стан {q1, q2}; переходи, що вели в стани q1 або q2, тепер вестимуть у новий стан, і те саме стосується переходів, що виходили зі станів q1 і q2. Отримаємо такий автомат:
Цей автомат, очевидно, допускає ту саму мову, що й попередній, і водночас має менше станів.
Еквівалентність станів
Нехай A = ⟨Q, Σ, δ, q0, F⟩ — автомат. Мову стану q ∈ Q, яку позначимо L(q), означимо як
Тобто ми змінюємо початковий стан автомата A з q0 на q і шукаємо мову, яку допускає такий автомат. Інакше кажучи, у мові L(q) лежать усі слова w, для яких в автоматі A зі стану q за словом w можна потрапити в заключний стан автомата. Якщо повернутися до попереднього автомата, то L(q1) = {1}.
Кажемо, що два різні стани q1 і q2 еквівалентні, якщо
Що це означає? Якщо стани q1, q2 еквівалентні, то, зробивши їх початковими станами автомата, ми отримаємо ту саму мову. Інакше кажучи: якщо автомат потрапляє в конфігурації ⟨q1, w⟩ і ⟨q2, w⟩, то в обох випадках він має або допустити слово, або в обох випадках відхилити.
Повернімося до попереднього автомата: стани q1 і q2 еквівалентні, бо коли ми в стані q1, то вхідне слово ще можна допустити лише тоді, коли непрочитана частина слова дорівнює «1». Те саме, якщо ми в стані q2.
Отже, мінімізація автомата полягає в тому, щоб знайти еквівалентні стани й позбутися їх, об'єднавши в один новий стан так само, як ми зробили в прикладі вище.
Як знайти еквівалентні стани
Які стани точно не будуть еквівалентними? Заключний і незаключний стани точно не еквівалентні, бо мова заключного стану відрізняється від мови незаключного: заключний стан неодмінно допускає слово ε, а незаключний — ні. Спосіб покажемо одразу на прикладі. Нехай маємо такий автомат:
Почнемо зі створення двох множин станів
Тепер складемо таблицю переходів і збережемо інформацію про групи S1 і S2:
Тепер перетворимо таблицю: замість того щоб записувати, у які стани ми потрапляємо за даним символом, позначимо лише групу, у яку ми переходимо. Наприклад, зі стану q3 за символом 0 ми потрапляємо в стан q5, який належить до групи S2. Тому замість q5 запишемо в таблицю S2:
Тепер далі розділимо обидві групи. В одну групу покладемо ті стани, які для всіх символів переходять в одні й ті самі групи. Наприклад, стани q3 і q6 не будуть в одній групі, бо ні за символом 0, ні за символом 1 вони не йдуть в одну групу. Натомість стани q1 і q2 будуть в одній групі, бо в обох немає переходу за символом 0, а за символом 1 обидва йдуть у групу S1. Створимо такі нові групи:
У кожній групі переходи однакові. Позначимо нові групи й знову з'ясуємо, до якої з цих нових груп переходять стани:
Тепер знову розділяємо групи. Але бачимо, що жодного подальшого поділу вже не зробити, ми отримали б ті самі групи: стани q1 і q2 мають однакові переходи між групами, але вони вже в одній групі, а іншого стану в групі S4 немає. Алгоритм пошуку еквівалентних станів завершено. З кожної групи достатньо вибрати один стан, решту видалити, а всі переходи, що вели у видалені стани, вестимуть у той один стан, який ми вибрали.
Можемо вибрати, що наш новий автомат матиме стани q3, q6, q0, q1, q4, а стани q2 і q5 вилучимо. Усі переходи, що вели в q2, тепер вестимуть у q1, а всі переходи, що вели в q5, вестимуть у q4:
Алгоритм мінімізації автомата
- Вилучаємо недосяжні стани,
- вилучаємо надлишкові стани,
- вилучаємо еквівалентні стани.
Джерела
- M. Sipser: Introduction to the Theory of Computation
- Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools
- Minimalizace automatů [PDF], чеською
Розділи: Недосяжні стани, Надлишкові стани, Мінімізація автомата