Симуляція недетермінованого автомата
Якщо маємо недетермінований автомат і хочемо дізнатися, чи допускає він дане слово, можна перетворити автомат на детермінований, можна якось спробувати, а можна використати алгоритм, який симулюватиме роботу НСА.
Принцип алгоритму
Принцип наочно покажемо на відповідному прикладі. Маємо такий автомат:
Це недетермінований скінченний автомат, який допускає певну мову. Яку саме, нам зараз зовсім не важливо. Покажемо, як може виглядати обчислення такого автомата для вхідного слова 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. Отримуємо пару ⟨{q3, q5}, ε⟩:
Тепер автомат прочитав усе слово й «перебуває» у двох станах: q3, q5. Оскільки принаймні один із них заключний, автомат слово 11001 допускає.
Алгоритм
Спочатку нам потрібна функція, яка приймає як параметр множину станів і обчислює, у які стани ми ще можемо потрапити за допомогою ε-переходів. Вхід — це автомат ⟨Q, Σ, δ, q0, F⟩ і множина станів States, а вихід — надмножина цих станів, у які можна потрапити за допомогою ε-переходів. Цю операцію називатимемо ε-замиканням множини States.
Цю функцію використаємо у функції, що симулюватиме роботу недетермінованого автомата. Вхід — автомат, вхідне слово w = w1w2… wn і множина станів, у яких автомат зараз перебуває. Вихід — відповідь Так або Ні залежно від того, чи допускає автомат дане слово.
Якщо хочемо перевірити, чи допускає автомат слово w, викликаємо функцію так: ComputeNFA(⟨Q, Σ, δ, q0, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q0, F⟩, {q0})).
Джерела
Розділи: Скінченний автомат, Повний автомат, Недетермінований скінченний автомат, Симуляція недетермінованого автомата, Перетворення НСА на ДСА