✖

Недосяжні стани

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

Приклад недосяжних станів

Нехай маємо такий автомат:

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

…то, звісно, обидва стани q3 і q4 були б недосяжними.

Означення недосяжного стану

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

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

Стан q ∈ Q недосяжний, якщо він не є досяжним.

Як вилучити недосяжні стани

Якщо автомат уже має недосяжні стани, їх варто вилучити. Для цього побудуємо еквівалентний автомат A′ = ⟨Q′, Σ, δ′, q0, F′⟩ без недосяжних станів.

Множину досяжних станів будуватимемо ітеративно. Почнемо з множини S0 = {q0}, адже початковий стан, безперечно, досяжний. Наступну множину будуємо так:

Si={r|δ(q,a)=r для якихось q∈Si−1,a∈Σ}∪Si−1

Словами: множина S0 завжди задана, а множину S1 будуємо так: беремо всі стани з множини S0 і дивимося, куди з них ведуть переходи для всіх символів з Σ. Ці стани об'єднуємо з вихідною множиною станів S0. Так само знаходимо множину S2 і наступні. Очевидно, що Si − 1 ⊆ Si.

Множину досяжних станів тоді можна отримати так:

⋃i=1∞Si

Може здатися дивним, що ми об'єднуємо нескінченно багато множин Si, проте автомат має лише скінченну кількість станів. Тож у якийсь момент множини Sj, Sj + 1 і всі наступні збігатимуться, і навіть після об'єднання нескінченно багатьох множин ми отримаємо скінченну множину станів.

Повернімося до автомата

і спробуймо знайти множину досяжних станів. Почнемо з базової рівності

S0={q0}

Тепер обчислимо множину S1. Для цього потрібно знайти всі переходи зі стану q0 і додати їхні цільові стани до множини S0. Оскільки q0 → a q1 і q0 → bq2, множина S1 додатково міститиме стани q1 і q2:

S1={q0,q1,q2}

Далі побудуємо множину S2. Подивимося, куди ми можемо потрапити зі станів q0, q1, q2. Єдиний новий стан — q5, у який можна потрапити зі стану q1:

S2={q0,q1,q2,q5}

Далі побудуємо множину S3. Чи можна зі станів q0, q1, q2, q5 потрапити в якийсь новий стан? Не можна, тож множина S3 міститиме ті самі елементи, що й S2:

S3={q0,q1,q2,q5}

Оскільки S2 = S3, то й S3 = S4 = S5 = … Якщо об'єднати всі Si, отримаємо множину S2, бо жоден новий елемент уже не з'явиться в жодній наступній множині.

Множина досяжних станів автомата дорівнює {q0, q1, q2, q5}. Недосяжні стани отримаємо простою різницею множин:

Q∖⋃i=1∞Si

Множина недосяжних станів нашого автомата — {q3, q4}. Вилучимо з автомата A усі недосяжні стани та всі переходи, що містили якийсь недосяжний стан. Тобто автомат A′ = ⟨Q′, Σ, δ′, q0, F′⟩ без недосяжних станів, еквівалентний автомату A = ⟨Q, Σ, δ, q0, F⟩, означимо так:

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
  • F′=F∩Q′=F∩⋃i=1∞Si

Джерела

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