Симулация на недетерминиран автомат

Ако имаме недетерминиран автомат и искаме да разберем дали приема дадена дума, можем да преобразуваме автомата в детерминиран, можем да го опитаме по някакъв начин или можем да използваме алгоритъм, който ще симулира работата на НКА.

Принцип на алгоритъма

Принципа ще покажем нагледно на подходящ пример. Нека имаме този автомат:

Това е недетерминиран краен автомат, който приема някакъв език. В момента изобщо не е нужно да се интересуваме какъв. Ще покажем как може да изглежда изчислението на такъв автомат за входната дума 11001. Идеята е такава: обработваме символ от думата и гледаме къде можем да отидем благодарение на няколкото прехода за един и същ символ. Запомняме всички тези състояния и в следващата стъпка вече приемаме, че сме „във всички тези състояния едновременно“, и ни интересува накъде можем да продължим от тези състояния.

Така ще помним множество от състояния, в които можем да се намираме, и непрочетената част от думата. В началото следователно имаме двойката ⟨{q₀}, 11001⟩. Започваме в състоянието q₀ (начално състояние) и на входа е думата 11001. Автоматът изглежда така, в червено и с удебелен шрифт е откроено състоянието, в което се намираме:

Първият символ е 1, от състоянието q₀ има само един преход за символа 1, така че стигаме до състоянието q₁. Запомняме двойката ⟨{q₁}, 1001⟩. Автоматът изглежда така:

Продължаваме нататък. Непрочетената част от думата е 1001, така че отново търсим преходи за 1. Те вече са два — обратно към състоянието q₀ и към състоянието q₃. Сега ще тръгнем към двете състояния едновременно. Запомняме двойката ⟨{q₀, q₃}, 001⟩.

Каква е логиката на това? Знаем, че съществува път, по който от началното състояние с думата 11 можем да стигнем както до състоянието q₃, така и до състоянието q₀. Все още не знаем кой клон ще ни влезе в работа, затова просто запомняме и двата. Продължаваме нататък. На входа имаме символа 0. Сега трябва да гледаме както преходите от q₀, така и преходите от q₃. От състоянието q₀ водят преходи към състоянията q₁ и q₂, от състоянието q₃ води преход обратно към q₁. Отчитаме всички тези състояния, с което получаваме двойката ⟨{q₁, q₂}, 01⟩:

В тази стъпка обаче още не сме свършили. Виждаме, че от състоянието q₂ води ε-преход към състоянието q₄. Знаем, че по ε-преход можем да „минем по всяко време“, без да четем следващ знак. С други думи — без да прочетем следващия символ от входната дума, можем още да преминем в състоянието q₄. Добавяме следователно състоянието q₄ към състоянията, в които можем да се намираме: ⟨{q₁, q₂, q₄}, 01⟩. Автоматът бихме оцветили така:

Нататък на входа е 0. Гледаме накъде можем да преминем от трите състояния, в които сме. От q₁ не можем да преминем никъде, защото липсва преход за 0. Изчислението в този клон свършва. От състоянието q₄ също не стигаме никъде. От състоянието q₂ стигаме обратно до състоянието q₂. Но тъй като от състоянието q₂ отново води ε-преход към състоянието q₄, можем да стигнем и до състоянието q₄. От множеството състояния {q₁, q₂, q₄} за символа 0 следователно можем да стигнем до множеството състояния {q₂, q₄}, получаваме двойката ⟨{q₂, q₄}, 1⟩:

Накрая на входа е символът 1. От състоянието q₂ не стигаме никъде, изчислението в този клон свършва. От състоянието q₄ обаче стигаме до състоянията q₃ и q₅. Получаваме двойката ⟨{q₃, q₅}, ε⟩:

Автоматът вече е прочел цялата дума и „се намира“ в две състояния: q₃, q₅. Тъй като поне едно от тях е крайно състояние, автоматът приема думата 11001.

Алгоритъм

Първо ни трябва функция, която приема като параметър множество от състояния и пресмята до кои състояния можем да стигнем още с помощта на ε-преходи. Входът следователно е автоматът ⟨Q, Σ, δ, q₀, F⟩ и множеството от състояния States, а изходът е надмножество на тези състояния, до което се стига с помощта на ε-преходи. Тази операция ще наричаме ε-затваряне на множеството States.

$\begin{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

Тази функция ще използваме във функция, която ще симулира работата на недетерминирания автомат. Входът е автоматът, входната дума w = w₁w₂… w_n и множеството от състояния, в които автоматът се намира в момента. Изходът е отговор Да или Не, според това дали автоматът приема, или не приема дадената дума.

$\begin{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return YES \\ Else \\ Return NO \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

Ако искаме да проверим дали автоматът приема думата w, извикваме функцията така: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

Източници

Глави: Краен автомат, Тотален автомат, Недетерминиран краен автомат, Симулация на недетерминиран автомат, Преобразуване на НКА в ДКА

« Предишна: Недетерминиран краен автомат

Следваща: Преобразуване на НКА в ДКА »