Симуляція недетермінованого автомата
Kapitoly: Скінченний автомат, Повний автомат, Недетермінований скінченний автомат, Симуляція недетермінованого автомата, Перетворення НСА на ДСА
Якщо маємо недетермінований автомат і хочемо дізнатися, чи допускає він дане слово, можна перетворити автомат на детермінований, можна якось спробувати, а можна використати алгоритм, який симулюватиме роботу НСА.
Принцип алгоритму
Принцип наочно покажемо на відповідному прикладі. Маємо такий автомат:
Це недетермінований скінченний автомат, який допускає певну мову. Яку саме, нам зараз зовсім не важливо. Покажемо, як може виглядати обчислення такого автомата для вхідного слова 11001. Міркування таке: обробляємо символ зі слова й дивимося, куди ми можемо потрапити завдяки кільком переходам для того самого символу. Запам'ятовуємо всі ці стани, а в наступному кроці вже вважаємо, що ми «в усіх цих станах одночасно», і нас цікавить, куди з цих станів можна піти далі.
Отже, ми пам'ятатимемо множину станів, у яких можемо перебувати, і не прочитану частину слова. На початку маємо пару <{q0}, 11001>. Починаємо в стані q0 (початковий стан), а на вході слово 11001. Автомат виглядає так, червоним і жирним виділено стан, у якому ми перебуваємо:
Перший символ — 1, зі стану q0 є лише один перехід для символу 1, тож потрапляємо в стан q1. Запам'ятовуємо пару <{q1}, 1001>. Автомат виглядає так:
Продовжуємо. Не прочитана частина слова має вигляд 1001, тож знову шукаємо переходи для 1. Їх уже два — назад у стан q0 і далі в стан q3. Тепер ми вирушаємо в обидва стани одночасно. Запам'ятовуємо пару <{q0, q3}, 001>.
У чому логіка? Ми знаємо, що існує шлях, яким із початкового стану за допомогою слова 11 можна потрапити і в стан q3, і в стан q0. Поки що ми не знаємо, яка гілка нам стане в пригоді, тож просто запам'ятовуємо обидві. Продовжуємо. На вході символ 0. Тепер треба дивитися і на переходи зі стану q0, і на переходи зі стану q3. Зі стану q0 ведуть переходи в стани q1 і q2, зі стану q3 веде перехід назад у q1. Враховуємо всі ці стани й отримуємо пару <{q1, q2}, 01>:
Але в цьому кроці ми ще не закінчили. Бачимо, що зі стану q2 веде ε-перехід у стан q4. Ми знаємо, що ε-переходом можна «піти будь-коли», не читаючи наступного знака. Іншими словами, не прочитавши наступного символу вхідного слова, ми можемо ще перейти в стан q4. Тож додаємо стан q4 до станів, у яких можемо перебувати: <{q1, q2, q4}, 01>. Автомат ми б розфарбували так:
Далі на вході 0. Дивимося, куди можна перейти з тих трьох станів, у яких ми перебуваємо. З q1 нікуди перейти не можна, бо немає переходу для 0. Обчислення в цій гілці закінчується. Зі стану q4 також нікуди не потрапимо. Зі стану q2 потрапимо назад у стан q2. Але оскільки зі стану q2 знову веде ε-перехід у стан q4, можемо потрапити і в стан q4. Із множини станів {q1, q2, q4} для символу 0 ми, отже, потрапляємо в множину станів {q2, q4}, отримуємо пару <{q2, q4}, 1>:
Нарешті на вході символ 1. Зі стану q2 нікуди не потрапимо, обчислення в цій гілці закінчується. Зате зі стану q4 потрапляємо в стани q3 і q5. Отримуємо пару $\left<\left\{q_3, q_5\right\}, \varepsilon\right>$:
Тепер автомат прочитав усе слово й «перебуває» у двох станах: q3, q5. Оскільки принаймні один із них заключний, автомат слово 11001 допускає.
Алгоритм
Спочатку нам потрібна функція, яка приймає як параметр множину станів і обчислює, у які стани ми ще можемо потрапити за допомогою ε-переходів. Вхід — це автомат $\left<Q, \Sigma, \delta, q_0, F\right>$ і множина станів States, а вихід — надмножина цих станів, у які можна потрапити за допомогою ε-переходів. Цю операцію називатимемо ε-замиканням множини States.
$$\begin{align}\\ &\mathbf{Function} EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, States\right)\\ &\qquad NextStates \leftarrow \emptyset\\ &\qquad \mathbf{ForEach} q \in States \mathbf{Do}\\ &\qquad \qquad NextStates \leftarrow NextStates \cup \left\{q\right\} \cup \delta(q, \varepsilon)\\ &\qquad \mathbf{EndFor}\\ &\qquad \\ &\qquad \mathbf{If} NextStates \setminus States = \emptyset \mathbf{Do}\\ &\qquad \qquad \mathbf{Return} States\\ &\qquad \mathbf{Else}\\ &\qquad \qquad \mathbf{Return} EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, NextStates\right)\\ &\qquad \mathbf{EndIf}\\ &\mathbf{EndFunction}\\ &\end{align}$$
Цю функцію використаємо у функції, що симулюватиме роботу недетермінованого автомата. Вхід — автомат, вхідне слово w = w1w2… wn і множина станів, у яких автомат зараз перебуває. Вихід — відповідь Так або Ні залежно від того, чи допускає автомат дане слово.
$$\begin{align}\\ &\mathbf{Function} ComputeNFA\left(\left<Q, \Sigma, \delta, q_0, F\right>, w, States\right)\\ &\qquad \mathbf{If} w = \epsilon \mathbf{Do}\\ &\qquad \qquad \mathbf{If} States \cap F \ne \emptyset \mathbf{Do}\\ &\qquad \qquad \qquad \mathbf{Return} \mbox{YES}\\ &\qquad \qquad \mathbf{Else}\\ &\qquad \qquad \qquad \mathbf{Return} \mbox{NO}\\ &\qquad \qquad \mathbf{EndIf}\\ &\qquad \mathbf{EndIf}\\ &\qquad NextStates \leftarrow \emptyset\\ &\qquad \mathbf{ForEach} q \in States \mathbf{Do}\\ &\qquad \qquad NextStates \leftarrow NextStates \cup \delta(q, w_1)\\ &\qquad \mathbf{EndFor}\\ &\qquad NextStates \leftarrow EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, NextStates\right)\\ &\qquad \mathbf{Return} ComputeNFA\left(\left<Q, \Sigma, \delta, q_0, F\right>, w_2w_3\dots w_n, NextStates\right)\\ &\mathbf{EndFunction}\\ &\end{align}$$
Якщо хочемо перевірити, чи допускає автомат слово w, викликаємо функцію так: $ComputeNFA\left(\left<Q, \Sigma, \delta, q_0, F\right>, w, EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, \left\{q_0\right\}\right)\right)$.