Надлишкові стани
Kapitoly: Недосяжні стани, Надлишкові стани, Мінімізація автомата
Скінченний автомат може мати стани, з яких неможливо потрапити в заключний стан, тож вони непотрібні. Такі стани називаємо надлишковими. Зазвичай ми хочемо їх вилучити, бо вони лише без потреби ускладнюють весь автомат.
Приклад надлишкових станів
Нехай маємо такий скінченний автомат:
Бачимо, що щойно ми потрапимо в стан q4 або q5, нам уже ніколи не вдасться дістатися до жодного із заключних станів q1 чи q2. Тому такі стани надлишкові, і ми можемо просто їх вилучити та отримати новий автомат, який буде еквівалентним; він допускатиме ту саму мову. Після вилучення надлишкових станів автомат виглядатиме так:
Він допускатиме ту саму мову. Проте бувають випадки, коли надлишкові стани мати доцільно — наприклад, коли ми будуємо повний автомат.
Означення надлишкового стану
Нехай $A=\left<Q, \Sigma, \delta, q_0, F\right>$ — скінченний автомат. Кажемо, що стан q ∈ Q надлишковий, якщо не існує жодного слова $w \in \Sigma^\ast$ і жодного стану qf ∈ F таких, що
$$ \left<q, w\right>\mapsto^\ast\left<q_f,\varepsilon\right>. $$
Як вилучити надлишкові стани
Припускаємо, що на вході маємо автомат $A=\left<Q, \Sigma, \delta, q_0, F\right>$, який уже не має недосяжних станів. Поступово знаходитимемо стани, що ведуть у заключні стани, потім стани, що ведуть у стани, які ведуть у заключні стани, і так далі. Так отримаємо множину всіх станів, які не є надлишковими. На початку покладемо S0 = F. Далі будуватимемо множини Si для i ∈ ℕ за таким правилом:
$$ S_i = \left\{q \in Q,|,\exists a \in \Sigma:\quad \delta(q, a)\in S_{i-1}\right\}\cup S_{i-1} $$
Підсумкову множину всіх станів, які не є надлишковими, можна записати так:
$$ \bigcup_{i=1}^{\infty}S_i. $$
А множину надлишкових станів — так:
$$ Q \setminus \bigcup_{i=1}^{\infty}S_i. $$
Інакше кажучи: якщо Si = Si + 1, то множина Q∖ Si містить надлишкові стани. Проілюструємо спосіб на такому автоматі:
Спершу покладемо S0 = {q1, q2}. Далі побудуємо множину S1: додамо до множини S0 усі стани, що ведуть в один зі станів множини S0. Додаємо стани q0 і q3, бо зі стану q0 веде перехід у q1, а зі стану q3 — у q2. Отримуємо S1 = {q0, q1, q2, q3}. Оскільки S0 ≠ S1, продовжуємо.
Побудуємо множину S2. Шукаємо всі стани, з яких можна потрапити в S1 і яких ще немає в S1. Такий стан лише один — q6, з якого можна потрапити в стан q3. Отримуємо S2 = {q0, q1, q2, q3, q6}. Оскільки S1≠ S2, продовжуємо.
Побудуємо множину S3. Чи існує якийсь новий стан, з якого можна потрапити в один зі станів множини S2? Не існує: зі станів q4 і q5 не можна потрапити в жоден зі станів множини S2, а решта станів уже є в S2. Отже, S3 = {q0, q1, q2, q3, q6}. Оскільки S2 = S3, алгоритм завершується, і множина S2 є множиною станів, які не є надлишковими. Множина {q4, q5} — це множина станів, які надлишкові.
Формально новий еквівалентний автомат без надлишкових станів будуємо так. Маємо автомат $A=\left<Q, \Sigma, \delta, q_0, F\right>$ і будуємо еквівалентний йому автомат $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F\right>$ без надлишкових станів.
- $Q^\prime = \bigcup_{i=1}^\infty S_i$
- $\forall q \in Q^\prime, a\in \Sigma:\quad \delta^\prime(q, a) = \delta(q, a)$, якщо $\delta(q, a) \in Q^\prime$, інакше $\delta^\prime(q, a)$ не означено