Перетворення НСА на ДСА
Покажемо, як перетворити недетермінований автомат на детермінований, і тим самим доведемо, що обчислювальна потужність недетермінованих і детермінованих автоматів однакова.
Основна ідея
Нехай маємо недетермінований автомат ⟨QN, ΣN, δN, q0, FN⟩ без ε-переходів. Побудуємо детермінований автомат ⟨QD, ΣD, δD, p0, FD⟩ так, що
- QD ⊆ 2QN
- ΣD = ΣN
- p0 = {q0}
- FD = {Q ∈ QD | Q ∩ FN ≠ ∅}
Функцію переходів δD означимо так:
Що це означає? Недетермінований автомат може перебувати одразу в кількох станах, тож, наприклад, він може опинитися в станах {q0, q1}. Прочитавши наступний символ, скажімо 1, він може потрапити в множину станів {q0, q2, q3}. У детермінованій версії того самого автомата це виглядає так: ми створюємо два стани, називаємо їх {q0, q1} і {q0, q2, q3} та проводимо між ними перехід для символу 1. Формально ми переходимо з одного стану в інший, але завдяки назвам знаємо, що в недетермінованому автоматі ми опинилися б відповідно у двох і в трьох станах.
Приклад
Нехай маємо такий недетермінований автомат:
Щоб побудувати детермінований автомат, насамперед потрібно побудувати нову функцію переходів. У цьому допоможе таблиця, до якої ми запишемо всі переходи. На початку таблиця виглядає так:
У лівому стовпці наприкінці алгоритму будуть усі стани детермінованого автомата. Заповнена таблиця задаватиме функцію переходів. Тепер запишемо в таблицю, у які стани ми потрапимо зі стану {q0}, якщо на вході символи 0 і 1.
Зі стану q0 для символу 0 веде перехід лише в стан q1, а для символу 1 — у стани q1 і q2. Тепер додамо до таблиці два нові стани: {q1} і {q1, q2}. Чому? Щойно ми вписуємо в таблицю якусь множину станів, якої ще немає в лівому стовпці, ми додаємо цю множину й туди.
і знову заповнюємо. Для стану {q1, q2} не забудь перевірити обидва стани, тобто взяти те, куди ми потрапимо зі стану q1, об'єднане з тим, куди ми потрапимо зі стану q2.
Ми отримали кілька нових станів, які треба додати до таблиці:
…і знову доповнюємо переходи:
Стани {q0, q1, q3}, {q1} і {q1,q2} у таблиці вже є, тож додаємо лише стан {q0,q1,q2,q3}.
Нових станів ми більше не додали, тож таблицю заповнено. Тепер залишилося побудувати діаграму. Стани детермінованого автомата — у першому стовпці, переходи для символів 0 і 1 — у наступних. Кожен стан, що містить якийсь заключний стан вихідного автомата, буде заключним і в цьому автоматі. Тобто заключним буде кожен стан, який містить q3. Автомат виглядатиме так:
Переконаймося, що автомат працює правильно. Спробуймо допустити слово «11001». У детермінованому автоматі ми підемо шляхом
і автомат допустить слово, бо останній стан {q0, q1, q2, q3} є заключним. У недетермінованому автоматі під час симуляції ми потрапили б у ті самі стани: почали б у стані q0, а для символу 1 потрапили б у стани {q1, q2}. Наступний символ 1 привів би нас у стани {q0,q3} і так далі. Зрештою ми опинилися б в усіх станах {q0, q1, q2, q3}, і автомат допустив би слово.
Джерела
Розділи: Скінченний автомат, Повний автомат, Недетермінований скінченний автомат, Симуляція недетермінованого автомата, Перетворення НСА на ДСА