Недетермінований скінченний автомат

Скінченний автомат, поданий у попередніх розділах (скорочено СА або ДСА), завжди був детермінований, що проявлялося в тому, що в кожен момент було зрозуміло, що зробить автомат. Тепер розглянемо загальніше поняття недетермінованих скінченних автоматів (скорочено НСА), у яких можуть існувати переходи, що виходять із того самого стану й задані для того самого символу.

Приклад

Подивись на таку діаграму автомата:

Що в ній дивного? Те, що з вузла q₀ ведуть два ребра для символу 0. Тож якщо ми спробуємо допустити слово 001, може здатися, що автомат не знатиме, чи має залишитися в стані q₀, чи йти за переходом у q₁. Такий автомат був би недетермінований.

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

Як же автомат вирішує? Недетермінований автомат завжди обирає (інколи кажуть «вгадує») той перехід, який приведе до того, що слово буде допущене, якщо це можливо.

Якщо подати в автомат слово 001, то в автомата є такі можливості, як вчинити зі словом:

\begin{eqnarray} q_0 \rightarrow q_0 \rightarrow q_0 \rightarrow q_0\\ q_0 \rightarrow q_0 \rightarrow q_1 \rightarrow q_2 \end{eqnarray}

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

Як він автоматично обирає «сприятливу» гілку? Можна уявити, що недетермінований автомат проходить усі можливі гілки, і якщо знаходить гілку, у якій слово допускається, то слово допускає. Як він може пройти всі гілки? Просто в момент, коли автомат у стані, з якого для поточного символу виходить n ребер, він n разів копіює сам себе, і кожна копія йде іншим шляхом. Так ми поступово перебираємо всі можливості.

Деревоподібне зображення обчислення автомата

Трохи змінимо попередній автомат:

Недетермінізм залишається в першому стані. Попередній автомат допускав усі слова, що закінчуються на 01. Цей змінений автомат допускає всі слова, що містять підслово 01. Отже, він допускає, наприклад, слово 101 або 0101. Усі гілки обчислення можна легко зобразити за допомогою дерева, наприклад для слова 01010 дерево могло б виглядати так:

На початку ми в початковому стані q₀. На вході слово 01010, перший непрочитаний знак — 0. Зі стану q₀ ведуть два переходи для символу 0, у стани q₀ і q₁. Тож у цьому вузлі дерево матиме двох нащадків: q₀ і q₁. Далі читаємо символ 1. Тут жодної неоднозначності немає, переходимо в стани q₀ і q₂. Далі читаємо знак 0, у лівій гілці знову виникає неоднозначність, ділимо обчислення ще на дві гілки. В одній знову залишаємося в q₀, а в іншій ідемо в q₁. І так далі.

Зауваж, що загалом дві гілки закінчуються в стані q₂, тобто в заключному стані. Існують дві гілки обчислення, якими автомат може допустити дане слово. Отже, цей автомат слово 01010 допустив би. Можемо спробувати побудувати подібне дерево для слова 1000.

Обчислення або залишається в стані q₀, або переходить у стан q₁, але звідти йому вже нікуди йти, бо на вході залишилися самі нулі, а стан q₁ має перехід лише для символу 1. Жодна гілка обчислення не закінчується в заключному стані, тож автомат слово 1000 не допускає.

ε-переходи

У недетермінованих автоматах можна додатково використовувати ще ε-переходи. Це переходи, які можна виконати за будь-якого символу на вході, причому не читаючи жодного символу зі слова. Як би ми могли записати недетермінований автомат, який допускав би порожнє слово, всі слова, що складаються лише з одиниць, і слова вигляду (10)ⁿ, тобто 10, 1010, …?

Ми розділили автомат на два «підавтомати». Верхній відповідає за розпізнавання слів, що складаються з 1, нижній — за слова вигляду (10)ⁿ. Спробуємо допустити слово 111. На початку автомат перебуває в стані q₀, а на вході має слово 111. Оскільки йому доступні ε-переходи, він може вирішити перейти в стан q₁ або q₂ залежно від того, що йому зручніше. Бачимо, що йому буде зручно перейти в стан q₁. Автомат переходить туди. При цьому на вході в нього досі слово 111! Лише в цей момент він починає читати символи зі слова й переходити зі стану q₁ знову в q₁, доки не прочитає все слово й не допустить його.

Якби ми спробували допустити 1010, автомат на початку перейшов би в стан q₂ і лише звідти почав би обробляти символи, і знову допустив би слово.

Для слова 1100 автомат міг би робити що завгодно — допустити таке слово він не може.

ε-переходи та недетермінізм у багатьох випадках полегшують нам роботу; наприклад, доведення того, що об'єднання регулярних мов — знову регулярна мова, з ε-переходами записати значно простіше, ніж у випадку детермінованих скінченних автоматів. У тому доведенні ми мали приклади таких автоматів

та

а далі побудували скінченний детермінований автомат, який допускав об'єднання обох мов. З ε-переходами такий автомат можна скласти так:

Просто додаємо новий початковий стан, з якого ведуть два ε-переходи в початкові стани вихідних автоматів, і це все. Автомат недетерміновано вирішує, чи спробувати допустити слово одним, чи другим «підавтоматом».

Означення недетермінованого автомата

Ми вже показали, чим відрізняються детермінований і недетермінований скінченні автомати, залишилося це формалізувати. Детермінований скінченний автомат ми означили як п'ятірку $\left<Q, \Sigma, \delta, q_0, F\right>$, де Q — множина станів, $\Sigma$ — алфавіт, δ — функція переходів, q₀ — початковий стан, а F — множина заключних станів. Єдине, що змінюється в означенні недетермінованих автоматів, — означення функції переходів.

У детермінованій версії функція для виклику δ(q, w) могла повернути лише один стан, тоді як у недетермінованій версії може повернути кілька станів — якщо для одного символу означено кілька переходів. Оскільки нам треба означити й ε-переходи, позначимо множину $\Sigma\cup\left\{\varepsilon\right\}$ як множину $\Sigma_\varepsilon$, тобто $\Sigma_\varepsilon=\Sigma\cup\left\{\varepsilon\right\}$. Функцію δ тоді означимо як

$$ \delta: Q \times \Sigma_\varepsilon\rightarrow 2^Q $$

Запис 2^Q позначає булеан, множину всіх підмножин множини Q. Формалізація обчислення дуже подібна до скінченних автоматів. Конфігурація автомата знову є парою $\left<q, w\right> \in Q \times \Sigma^\ast$. Крок обчислення $\mapsto$ — це відношення на множині конфігурацій таке, що

$$ \left<q_i, w_0w_1\dots w_n\right> \mapsto \left<q_j, w_1\dots w_n\right>, $$

тоді й лише тоді, коли q_j ∈ δ(q_i, w₀). У цьому реченні й була найбільша відмінність. У детермінованих автоматах ми записували цю умову як q_j = δ(q_i, w₀), бо функція δ завжди повертала один стан. Недетермінована версія функції переходів повертає множину станів, тому там стоїть символ ∈. Рефлексивне й транзитивне замикання відношення ми знову позначатимемо $\mapsto^\ast$. Скажемо, що автомат допускає слово w тоді й лише тоді, коли існує q_f ∈ F таке, що

$$\left<q_0, w\right> \mapsto^\ast \left<q_f, \varepsilon\right>.$$

Джерела

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