✖

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

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

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

Приклад

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

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

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

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

Нехай $A=\left<Q, \Sigma, \delta, q_0, F\right>$ — автомат. Мову стану q∈ Q, яку позначимо L(q), означимо як

$$ L(q) = L(\left<Q, \Sigma, \delta, q, F\right>) $$

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

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

$$ L(q_1) = L(q_2) $$

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

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

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

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

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

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

\begin{eqnarray} S_1&=&F=\left\{q_3, q_6\right\},\\ S_2&=&Q\setminus F=\left\{q_0, q_1, q_2, q_4, q_5\right\}. \end{eqnarray}

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

$$ \begin{array}{c|c|cc|c} \text{група}&\text{стан}&0&1\\\hline S_1&q_3&q_5&q_4\\ &q_6&—&—\\\hline S_2&q_0&q_1&q_2\\ &q_1&—&q_3\\ &q_2&—&q_3\\ &q_4&q_6&—\\ &q_5&q_6&—\\ \end{array} $$

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

$$ \begin{array}{c|c|cc|c} \text{група}&\text{стан}&0&1\\\hline S_1&q_3&S_2&S_2\\ &q_6&—&—\\\hline S_2&q_0&S_2&S_2\\ &q_1&—&S_1\\ &q_2&—&S_1\\ &q_4&S_1&—\\ &q_5&S_1&—\\ \end{array} $$

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

$$ \begin{array}{c|c|cc|c} \text{група}&\text{стан}&0&1\\\hline &q_3&S_2&S_2\\\hline &q_6&—&—\\\hline &q_0&S_2&S_2\\\hline &q_1&—&S_1\\ &q_2&—&S_1\\\hline &q_4&S_1&—\\ &q_5&S_1&—\\ \end{array} $$

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

$$ \begin{array}{c|c|cc|c} \text{група}&\text{стан}&0&1\\\hline S_1&q_3&S_5&S_5\\\hline S_2&q_6&—&—\\\hline S_3&q_0&S_4&S_4\\\hline S_4&q_1&—&S_1\\ &q_2&—&S_1\\\hline S_5&q_4&S_2&—\\ &q_5&S_2&—\\ \end{array} $$

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

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

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

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

Джерела