Недосяжні стани
Kapitoly: Недосяжні стани, Надлишкові стани, Мінімізація автомата
Скінченний автомат може мати стани, у які неможливо потрапити. Такі стани називаємо недосяжними. Зазвичай ми хочемо їх вилучити, бо вони лише без потреби ускладнюють весь автомат.
Приклад недосяжних станів
Нехай маємо такий автомат:
Бачимо: хоч би що ми робили, у стан q3 ми ніколи не потрапимо, бо в нього не веде жоден перехід. Тому кажемо, що стан q3 недосяжний. Питання: чи був би стан q3 досяжним, якби в нього вів перехід з іншого стану? Якби ми провели ребро з одного зі станів q0, q1, q2, q5, то був би. А якби ми додали ще одну вершину й провели перехід з неї…
…то, звісно, обидва стани q3 і q4 були б недосяжними.
Означення недосяжного стану
Спершу означимо досяжний стан. Нехай $A=\left<Q, \Sigma, \delta, q_0, F\right>$ — скінченний автомат. Кажемо, що стан q ∈ Q досяжний, якщо існує слово $w \in \Sigma^\ast$ таке, що
$$ \left<q_0, w\right> \mapsto^\ast \left<q, \varepsilon\right>. $$
Стан q ∈ Q недосяжний, якщо він не є досяжним.
Як вилучити недосяжні стани
Якщо автомат уже має недосяжні стани, їх варто вилучити. Для цього побудуємо еквівалентний автомат $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F^\prime\right>$ без недосяжних станів.
Множину досяжних станів будуватимемо ітеративно. Почнемо з множини S0 = {q0}, адже початковий стан, безперечно, досяжний. Наступну множину будуємо так:
$$ S_i = \left\{r,|, \delta(q, a) = r \text{ для якихось } q \in S_{i-1}, a\in \Sigma \right\} \cup S_{i-1} $$
Словами: множина S0 завжди задана, а множину S1 будуємо так: беремо всі стани з множини S0 і дивимося, куди з них ведуть переходи для всіх символів з $\Sigma$. Ці стани об'єднуємо з вихідною множиною станів S0. Так само знаходимо множину S2 і наступні. Очевидно, що $S_{i-1} \subseteq S_{i}$.
Множину досяжних станів тоді можна отримати так:
$$ \bigcup_{i=1}^\infty S_i $$
Може здатися дивним, що ми об'єднуємо нескінченно багато множин Si, проте автомат має лише скінченну кількість станів. Тож у якийсь момент множини Sj, Sj + 1 і всі наступні збігатимуться, і навіть після об'єднання нескінченно багатьох множин ми отримаємо скінченну множину станів.
Повернімося до автомата
і спробуймо знайти множину досяжних станів. Почнемо з базової рівності
$$ S_0 = \left\{q_0\right\} $$
Тепер обчислимо множину S1. Для цього потрібно знайти всі переходи зі стану q0 і додати їхні цільові стани до множини S0. Оскільки $q_0\rightarrow^a q_1$ і $q_0\rightarrow^bq_2$, множина S1 додатково міститиме стани q1 і q2:
$$ S_1 = \left\{q_0, q_1, q_2\right\} $$
Далі побудуємо множину S2. Подивимося, куди ми можемо потрапити зі станів q0, q1, q2. Єдиний новий стан — q5, у який можна потрапити зі стану q1:
$$ S_2 = \left\{q_0, q_1, q_2, q_5\right\} $$
Далі побудуємо множину S3. Чи можна зі станів q0, q1, q2, q5 потрапити в якийсь новий стан? Не можна, тож множина S3 міститиме ті самі елементи, що й S2:
$$ S_3 = \left\{q_0, q_1, q_2, q_5\right\} $$
Оскільки S2 = S3, то й S3 = S4 = S5 = … Якщо об'єднати всі Si, отримаємо множину S2, бо жоден новий елемент уже не з'явиться в жодній наступній множині.
Множина досяжних станів автомата дорівнює {q0, q1, q2, q5}. Недосяжні стани отримаємо простою різницею множин:
$$ Q \setminus \bigcup_{i=1}^\infty S_i $$
Множина недосяжних станів нашого автомата — {q3, q4}. Вилучимо з автомата A усі недосяжні стани та всі переходи, що містили якийсь недосяжний стан. Тобто автомат $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F^\prime\right>$ без недосяжних станів, еквівалентний автомату $A=\left<Q, \Sigma, \delta, 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)$
- $F^\prime = F \cap Q^\prime = F \cap \bigcup_{i=1}^\infty S_i$