Недосяжні стани
Скінченний автомат може мати стани, у які неможливо потрапити. Такі стани називаємо недосяжними. Зазвичай ми хочемо їх вилучити, бо вони лише без потреби ускладнюють весь автомат.
Приклад недосяжних станів
Нехай маємо такий автомат:
Бачимо: хоч би що ми робили, у стан q3 ми ніколи не потрапимо, бо в нього не веде жоден перехід. Тому кажемо, що стан q3 недосяжний. Питання: чи був би стан q3 досяжним, якби в нього вів перехід з іншого стану? Якби ми провели ребро з одного зі станів q0, q1, q2, q5, то був би. А якби ми додали ще одну вершину й провели перехід з неї…
…то, звісно, обидва стани q3 і q4 були б недосяжними.
Означення недосяжного стану
Спершу означимо досяжний стан. Нехай A = ⟨Q, Σ, δ, q0, F⟩ — скінченний автомат. Кажемо, що стан q ∈ Q досяжний, якщо існує слово w ∈ Σ∗ таке, що
Стан q ∈ Q недосяжний, якщо він не є досяжним.
Як вилучити недосяжні стани
Якщо автомат уже має недосяжні стани, їх варто вилучити. Для цього побудуємо еквівалентний автомат A′ = ⟨Q′, Σ, δ′, q0, F′⟩ без недосяжних станів.
Множину досяжних станів будуватимемо ітеративно. Почнемо з множини S0 = {q0}, адже початковий стан, безперечно, досяжний. Наступну множину будуємо так:
Словами: множина S0 завжди задана, а множину S1 будуємо так: беремо всі стани з множини S0 і дивимося, куди з них ведуть переходи для всіх символів з Σ. Ці стани об'єднуємо з вихідною множиною станів S0. Так само знаходимо множину S2 і наступні. Очевидно, що Si − 1 ⊆ Si.
Множину досяжних станів тоді можна отримати так:
Може здатися дивним, що ми об'єднуємо нескінченно багато множин Si, проте автомат має лише скінченну кількість станів. Тож у якийсь момент множини Sj, Sj + 1 і всі наступні збігатимуться, і навіть після об'єднання нескінченно багатьох множин ми отримаємо скінченну множину станів.
Повернімося до автомата
і спробуймо знайти множину досяжних станів. Почнемо з базової рівності
Тепер обчислимо множину S1. Для цього потрібно знайти всі переходи зі стану q0 і додати їхні цільові стани до множини S0. Оскільки q0 → a q1 і q0 → bq2, множина S1 додатково міститиме стани q1 і q2:
Далі побудуємо множину S2. Подивимося, куди ми можемо потрапити зі станів q0, q1, q2. Єдиний новий стан — q5, у який можна потрапити зі стану q1:
Далі побудуємо множину S3. Чи можна зі станів q0, q1, q2, q5 потрапити в якийсь новий стан? Не можна, тож множина S3 міститиме ті самі елементи, що й S2:
Оскільки S2 = S3, то й S3 = S4 = S5 = … Якщо об'єднати всі Si, отримаємо множину S2, бо жоден новий елемент уже не з'явиться в жодній наступній множині.
Множина досяжних станів автомата дорівнює {q0, q1, q2, q5}. Недосяжні стани отримаємо простою різницею множин:
Множина недосяжних станів нашого автомата — {q3, q4}. Вилучимо з автомата A усі недосяжні стани та всі переходи, що містили якийсь недосяжний стан. Тобто автомат A′ = ⟨Q′, Σ, δ′, q0, F′⟩ без недосяжних станів, еквівалентний автомату A = ⟨Q, Σ, δ, q0, F⟩, означимо так:
- ∀q ∈ Q′, a ∈ Σ: δ′(q, a) = δ(q, a)
Джерела
Розділи: Недосяжні стани, Надлишкові стани, Мінімізація автомата