Надлишкові стани
Скінченний автомат може мати стани, з яких неможливо потрапити в заключний стан, тож вони непотрібні. Такі стани називаємо надлишковими. Зазвичай ми хочемо їх вилучити, бо вони лише без потреби ускладнюють весь автомат.
Приклад надлишкових станів
Нехай маємо такий скінченний автомат:
Бачимо, що щойно ми потрапимо в стан q4 або q5, нам уже ніколи не вдасться дістатися до жодного із заключних станів q1 чи q2. Тому такі стани надлишкові, і ми можемо просто їх вилучити та отримати новий автомат, який буде еквівалентним; він допускатиме ту саму мову. Після вилучення надлишкових станів автомат виглядатиме так:
Він допускатиме ту саму мову. Проте бувають випадки, коли надлишкові стани мати доцільно — наприклад, коли ми будуємо повний автомат.
Означення надлишкового стану
Нехай A = ⟨Q, Σ, δ, q0, F⟩ — скінченний автомат. Кажемо, що стан q ∈ Q надлишковий, якщо не існує жодного слова w ∈ Σ∗ і жодного стану qf ∈ F таких, що
Як вилучити надлишкові стани
Припускаємо, що на вході маємо автомат A = ⟨Q, Σ, δ, q0, F⟩, який уже не має недосяжних станів. Поступово знаходитимемо стани, що ведуть у заключні стани, потім стани, що ведуть у стани, які ведуть у заключні стани, і так далі. Так отримаємо множину всіх станів, які не є надлишковими. На початку покладемо S0 = F. Далі будуватимемо множини Si для 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 = ⟨Q, Σ, δ, q0, F⟩ і будуємо еквівалентний йому автомат A′ = ⟨Q′, Σ, δ′, q0, F⟩ без надлишкових станів.
- ∀q ∈ Q′, a ∈ Σ: δ′(q, a) = δ(q, a), якщо δ(q, a) ∈ Q′, інакше δ′(q, a) не означено
Джерела
Розділи: Недосяжні стани, Надлишкові стани, Мінімізація автомата