✖

Перетворення НСА на ДСА

Покажемо, як перетворити недетермінований автомат на детермінований, і тим самим доведемо, що обчислювальна потужність недетермінованих і детермінованих автоматів однакова.

Основна ідея

Нехай маємо недетермінований автомат ⟨QN, ΣN, δN, q0, FN⟩ без ε-переходів. Побудуємо детермінований автомат ⟨QD, ΣD, δD, p0, FD⟩ так, що

  • QD ⊆ 2QN
  • ΣD = ΣN
  • p0 = {q0}
  • FD = {Q ∈ QD | Q ∩ FN ≠ ∅}

Функцію переходів δD означимо так:

∀Q∈QD,a∈ΣD:δD(Q,a)=⋃q∈QδN(q,a)

Що це означає? Недетермінований автомат може перебувати одразу в кількох станах, тож, наприклад, він може опинитися в станах {q0, q1}. Прочитавши наступний символ, скажімо 1, він може потрапити в множину станів {q0, q2, q3}. У детермінованій версії того самого автомата це виглядає так: ми створюємо два стани, називаємо їх {q0, q1} і {q0, q2, q3} та проводимо між ними перехід для символу 1. Формально ми переходимо з одного стану в інший, але завдяки назвам знаємо, що в недетермінованому автоматі ми опинилися б відповідно у двох і в трьох станах.

Приклад

Нехай маємо такий недетермінований автомат:

Щоб побудувати детермінований автомат, насамперед потрібно побудувати нову функцію переходів. У цьому допоможе таблиця, до якої ми запишемо всі переходи. На початку таблиця виглядає так:

стан/символ01{q0}

У лівому стовпці наприкінці алгоритму будуть усі стани детермінованого автомата. Заповнена таблиця задаватиме функцію переходів. Тепер запишемо в таблицю, у які стани ми потрапимо зі стану {q0}, якщо на вході символи 0 і 1.

стан/символ01{q0}{q1}{q1,q2}

Зі стану q0 для символу 0 веде перехід лише в стан q1, а для символу 1 — у стани q1 і q2. Тепер додамо до таблиці два нові стани: {q1} і {q1, q2}. Чому? Щойно ми вписуємо в таблицю якусь множину станів, якої ще немає в лівому стовпці, ми додаємо цю множину й туди.

стан/символ01{q0}{q1}{q1,q2}{q1}{q1,q2}

і знову заповнюємо. Для стану {q1, q2} не забудь перевірити обидва стани, тобто взяти те, куди ми потрапимо зі стану q1, об'єднане з тим, куди ми потрапимо зі стану q2.

стан/символ01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}

Ми отримали кілька нових станів, які треба додати до таблиці:

стан/символ01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q3}

…і знову доповнюємо переходи:

стан/символ01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q3}{q1}{q1,q2}

Стани {q0, q1, q3}, {q1} і {q1,q2} у таблиці вже є, тож додаємо лише стан {q0,q1,q2,q3}.

стан/символ01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q3}{q1}{q1,q2}{q0,q1,q2,q3}{q0,q1,q3}{q0,q1,q2,q3}

Нових станів ми більше не додали, тож таблицю заповнено. Тепер залишилося побудувати діаграму. Стани детермінованого автомата — у першому стовпці, переходи для символів 0 і 1 — у наступних. Кожен стан, що містить якийсь заключний стан вихідного автомата, буде заключним і в цьому автоматі. Тобто заключним буде кожен стан, який містить q3. Автомат виглядатиме так:

Переконаймося, що автомат працює правильно. Спробуймо допустити слово «11001». У детермінованому автоматі ми підемо шляхом

q0→1q1,q2→1q0,q3→0q1→0q0,q1,q3→1q0,q1,q2,q3

і автомат допустить слово, бо останній стан {q0, q1, q2, q3} є заключним. У недетермінованому автоматі під час симуляції ми потрапили б у ті самі стани: почали б у стані q0, а для символу 1 потрапили б у стани {q1, q2}. Наступний символ 1 привів би нас у стани {q0,q3} і так далі. Зрештою ми опинилися б в усіх станах {q0, q1, q2, q3}, і автомат допустив би слово.

Джерела

Розділи: Скінченний автомат, Повний автомат, Недетермінований скінченний автомат, Симуляція недетермінованого автомата, Перетворення НСА на ДСА