✖

Мінімізація автомата

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

Приклад

Розгляньмо такий автомат:

Автомат допускає лише слова «01» і «11». Очевидно, що існує простіший автомат із трьома станами, який допускає ту саму мову. Стани q1 і q2 можна об'єднати в один новий стан {q1, q2}; переходи, що вели в стани q1 або q2, тепер вестимуть у новий стан, і те саме стосується переходів, що виходили зі станів q1 і q2. Отримаємо такий автомат:

Цей автомат, очевидно, допускає ту саму мову, що й попередній, і водночас має менше станів.

Еквівалентність станів

Нехай A = ⟨Q, Σ, δ, q0, F⟩ — автомат. Мову стану q ∈ Q, яку позначимо L(q), означимо як

L(q)=L(⟨Q,Σ,δ,q,F⟩)

Тобто ми змінюємо початковий стан автомата A з q0 на q і шукаємо мову, яку допускає такий автомат. Інакше кажучи, у мові L(q) лежать усі слова w, для яких в автоматі A зі стану q за словом w можна потрапити в заключний стан автомата. Якщо повернутися до попереднього автомата, то L(q1) = {1}.

Кажемо, що два різні стани q1 і q2 еквівалентні, якщо

L(q1)=L(q2)

Що це означає? Якщо стани q1, q2 еквівалентні, то, зробивши їх початковими станами автомата, ми отримаємо ту саму мову. Інакше кажучи: якщо автомат потрапляє в конфігурації ⟨q1, w⟩ і ⟨q2, w⟩, то в обох випадках він має або допустити слово, або в обох випадках відхилити.

Повернімося до попереднього автомата: стани q1 і q2 еквівалентні, бо коли ми в стані q1, то вхідне слово ще можна допустити лише тоді, коли непрочитана частина слова дорівнює «1». Те саме, якщо ми в стані q2.

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

Як знайти еквівалентні стани

Які стани точно не будуть еквівалентними? Заключний і незаключний стани точно не еквівалентні, бо мова заключного стану відрізняється від мови незаключного: заключний стан неодмінно допускає слово ε, а незаключний — ні. Спосіб покажемо одразу на прикладі. Нехай маємо такий автомат:

Почнемо зі створення двох множин станів

S1=F={q3,q6},S2=Q∖F={q0,q1,q2,q4,q5}.

Тепер складемо таблицю переходів і збережемо інформацію про групи S1 і S2:

групастан01S1q3q5q4q6——S2q0q1q2q1—q3q2—q3q4q6—q5q6—

Тепер перетворимо таблицю: замість того щоб записувати, у які стани ми потрапляємо за даним символом, позначимо лише групу, у яку ми переходимо. Наприклад, зі стану q3 за символом 0 ми потрапляємо в стан q5, який належить до групи S2. Тому замість q5 запишемо в таблицю S2:

групастан01S1q3S2S2q6——S2q0S2S2q1—S1q2—S1q4S1—q5S1—

Тепер далі розділимо обидві групи. В одну групу покладемо ті стани, які для всіх символів переходять в одні й ті самі групи. Наприклад, стани q3 і q6 не будуть в одній групі, бо ні за символом 0, ні за символом 1 вони не йдуть в одну групу. Натомість стани q1 і q2 будуть в одній групі, бо в обох немає переходу за символом 0, а за символом 1 обидва йдуть у групу S1. Створимо такі нові групи:

групастан01q3S2S2q6——q0S2S2q1—S1q2—S1q4S1—q5S1—

У кожній групі переходи однакові. Позначимо нові групи й знову з'ясуємо, до якої з цих нових груп переходять стани:

групастан01S1q3S5S5S2q6——S3q0S4S4S4q1—S1q2—S1S5q4S2—q5S2—

Тепер знову розділяємо групи. Але бачимо, що жодного подальшого поділу вже не зробити, ми отримали б ті самі групи: стани q1 і q2 мають однакові переходи між групами, але вони вже в одній групі, а іншого стану в групі S4 немає. Алгоритм пошуку еквівалентних станів завершено. З кожної групи достатньо вибрати один стан, решту видалити, а всі переходи, що вели у видалені стани, вестимуть у той один стан, який ми вибрали.

Можемо вибрати, що наш новий автомат матиме стани q3, q6, q0, q1, q4, а стани q2 і q5 вилучимо. Усі переходи, що вели в q2, тепер вестимуть у q1, а всі переходи, що вели в q5, вестимуть у q4:

Алгоритм мінімізації автомата

  1. Вилучаємо недосяжні стани,
  2. вилучаємо надлишкові стани,
  3. вилучаємо еквівалентні стани.

Джерела

Розділи: Недосяжні стани, Надлишкові стани, Мінімізація автомата