✖

Надлишкові стани

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

Приклад надлишкових станів

Нехай маємо такий скінченний автомат:

Бачимо, що щойно ми потрапимо в стан q4 або q5, нам уже ніколи не вдасться дістатися до жодного із заключних станів q1 чи q2. Тому такі стани надлишкові, і ми можемо просто їх вилучити та отримати новий автомат, який буде еквівалентним; він допускатиме ту саму мову. Після вилучення надлишкових станів автомат виглядатиме так:

Він допускатиме ту саму мову. Проте бувають випадки, коли надлишкові стани мати доцільно — наприклад, коли ми будуємо повний автомат.

Означення надлишкового стану

Нехай A = ⟨Q, Σ, δ, q0, F⟩ — скінченний автомат. Кажемо, що стан q ∈ Q надлишковий, якщо не існує жодного слова w ∈ Σ∗ і жодного стану qf ∈ F таких, що

⟨q,w⟩↦∗⟨qf,ε⟩.

Як вилучити надлишкові стани

Припускаємо, що на вході маємо автомат A = ⟨Q, Σ, δ, q0, F⟩, який уже не має недосяжних станів. Поступово знаходитимемо стани, що ведуть у заключні стани, потім стани, що ведуть у стани, які ведуть у заключні стани, і так далі. Так отримаємо множину всіх станів, які не є надлишковими. На початку покладемо S0 = F. Далі будуватимемо множини Si для i ∈ ℕ за таким правилом:

Si={q∈Q|∃a∈Σ:δ(q,a)∈Si−1}∪Si−1

Підсумкову множину всіх станів, які не є надлишковими, можна записати так:

⋃i=1∞Si.

А множину надлишкових станів — так:

Q∖⋃i=1∞Si.

Інакше кажучи: якщо 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′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a), якщо δ(q, a) ∈ Q′, інакше δ′(q, a) не означено

Джерела

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