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

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

Основна ідея

Нехай маємо недетермінований автомат $\left<Q_N, \Sigma_N, \delta_N, q_0, F_N\right>$ без $\varepsilon$-переходів. Побудуємо детермінований автомат $\left<Q_D, \Sigma_D, \delta_D, p_0, F_D\right>$ так, що

• Q_D ⊆ 2^Q_N
• $\Sigma_D = \Sigma_N$
• p₀ = {q₀}
• $F_D = \left\{Q \in Q_D,|,Q \cap F_N \ne \varnothing\right\}$

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

$$ \forall Q \in Q_D, a\in\Sigma_D: \delta_D(Q, a) = \bigcup_{q\in Q} \delta_N(q, a) $$

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

Приклад

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

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

$$ \begin{array}{c|c|c} \text{стан}/\text{символ}&0&1\\\hline \left\{q_0\right\} \end{array} $$

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

$$ \begin{array}{c|c|c} \text{стан}/\text{символ}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \end{array} $$

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

$$ \begin{array}{c|c|c} \text{стан}/\text{символ}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}\\ \left\{q_1, q_2\right\} \end{array} $$

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

$$ \begin{array}{c|c|c} \text{стан}/\text{символ}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \end{array} $$

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

$$ \begin{array}{c|c|c} \text{стан}/\text{символ}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}\\ \left\{q_0,q_3\right\}\\ \end{array} $$

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

$$ \begin{array}{c|c|c} \text{стан}/\text{символ}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \left\{q_0,q_3\right\}&\left\{q_1\right\}&\left\{q_1,q_2\right\}\\ \end{array} $$

Стани {q₀, q₁, q₃}, {q₁} і {q₁,q₂} у таблиці вже є, тож додаємо лише стан {q₀,q₁,q₂,q₃}.

$$ \begin{array}{c|c|c} \text{стан}/\text{символ}&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \left\{q_0,q_3\right\}&\left\{q_1\right\}&\left\{q_1,q_2\right\}\\ \left\{q_0,q_1,q_2,q_3\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \end{array} $$

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

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

$$ q_0 \rightarrow^1 q_1, q_2 \rightarrow^1 q_0, q_3 \rightarrow^0 q_1 \rightarrow^0 q_0, q_1, q_3 \rightarrow^1 q_0, q_1, q_2, q_3 $$

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

Джерела

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools