Преобразуване на НКА в ДКА

Ще покажем как да преобразуваме недетерминиран автомат в детерминиран автомат, с което ще докажем, че изчислителната мощ на недетерминираните и на детерминираните автомати е еквивалентна.

Основна идея

Нека имаме недетерминиран автомат ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ без ε-преходи. Построяваме детерминиран автомат ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ така, че

• Q_D ⊆ 2^Q_N
• Σ_D = Σ_N
• p₀ = {q₀}
• F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

Преходната функция δ_D определяме по следния начин:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\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}{ccc}\text{състояние}/\text{символ}& 0& 1\\ \left\{q_0\right\}\end{array}$$

В лявата колона в края на алгоритъма ще имаме всички състояния на детерминирания автомат. Попълнената таблица след това ще определя преходната функция. Сега записваме в таблицата до кои състояния стигаме, ако сме в състоянието {q₀} и на входа са символите 0 и 1.

$$\begin{array}{ccc}\text{състояние}/\text{символ}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

От състоянието q₀ за символа 0 води преход само към състоянието q₁, а за символа 1 води към състоянията q₁ и q₂. Сега добавяме в таблицата две нови състояния: {q₁} и {q₁, q₂}. Защо? Щом в таблицата попълним някакво множество от състояния, което още нямаме в лявата колона, добавяме това множество от състояния там.

$$\begin{array}{ccc}\text{състояние}/\text{символ}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

и отново попълваме. При състоянието {q₁, q₂} не бива да забравяме да проверим и двете състояния, т.е. накъде стигаме от състоянието q₁, обединено с това накъде стигаме от състоянието q₂.

$$\begin{array}{ccc}\text{състояние}/\text{символ}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

Получихме няколко нови състояния, които трябва да добавим в таблицата:

$$\begin{array}{ccc}\text{състояние}/\text{символ}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}\\ \{q_0,q_3\}\end{array}$$

…и пак попълваме преходите:

$$\begin{array}{ccc}\text{състояние}/\text{символ}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Състоянията {q₀, q₁, q₃}, {q₁} и {q₁,q₂} вече са в таблицата, така че добавяме само състоянието {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{състояние}/\text{символ}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

Не добавихме нито едно ново състояние, така че таблицата е попълнена. Остава само да съставим диаграмата. Състоянията на детерминирания автомат са в първата колона, преходите за символите 0 и 1 са в следващите. Всяко състояние, което съдържа някакво крайно състояние от първоначалния автомат, ще бъде крайно състояние и в този автомат. Т.е. всяко състояние, съдържащо q₃, ще бъде крайно. Автоматът ще изглежда така:

Можем да покажем, че автоматът наистина работи правилно. Ще опитаме да приемем думата 11001. В детерминирания автомат ще вървим по пътя

$$q_0{\to }^1{q}_1,q_2{\to }^1{q}_0,q_3{\to }^0{q}_1{\to }^0{q}_0,q_1,q_3{\to }^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