Determinizacja automatu skończonego

Determinizacja automatu skończonego – proces tworzenia deterministycznego automatu skończonego (DAS) z niedeterministycznego automatu skończonego (NAS). Transformacja taka jest zawsze możliwa i otrzymany w jej procesie automat akceptuje dokładnie ten sam język, co automat wejściowy. Jakkolwiek, gdy NAS ma $n$ stanów, wynikowy DAS może mieć do $2^n$ stanów, wykładniczo więcej, co czyni proces niepraktycznym dla dużych NAS.

Opis metody

Determinizacja niedeterministycznego automatu skończonego $N$ polega na konstrukcji deterministycznego automatu $D,$ który będzie symulował działanie $N.$ Automat $D$ po każdym przejściu pamięta zbiór wszystkich stanów, które $N$ mógłby osiągnąć w danym kroku. Jeżeli po zakończeniu działania ten zbiór zawiera jakikolwiek stan akceptujący, przeczytane słowo jest akceptowane. Stanami automatu $D$ stają się więc zbiory stanów $N.$

Formalna konstrukcja

Niech $N=(Q_N,f_N,q_0,F_N)$ nad alfabetem $\mathrm{\Sigma }$ będzie automatem niedeterministycznym o zbiorze stanów $Q_N,$ funkcji przejść $f_N:\mathrm{\Sigma }\to 𝒫(Q_N),$ stanie początkowym $q_0$ i zbiorze stanów akceptujących $F_N.$ Wtedy automat $D=(Q_D,f_D,\{q_0\},F_D)$ zdefiniowany w następujący sposób:

• $Q_D=𝒫(Q_N)$
• $f_D:Q_D\times \mathrm{\Sigma }\ni (S,a)\to \bigcup _{s\in S}{f}_N(s,a)\in Q_D$
• $F_D=\{S\in Q_D:S\cap F_N\ne \mathrm{\varnothing }\}$

jest deterministyczny i akceptuje ten sam język co $N.$

Przykład

NAS

Dany jest NAS:

• S_n={A,B,C}
• ∑_n={0,1}
• s_n=A
• A_n={C}

DAS

Odpowiadający mu DAS będzie miał 2^|S_n|=2³=8 stanów:

• S_d0={α,β,γ,αβ,αγ,βγ,αβγ,ω}

α odpowiada stanowi A, β stanowi B, a γ stanowi C

stan αβ będzie osiągany na przykład, gdy ze stanu A dla 0 na wejściu odpowiada jednocześnie przejście A→A i A→B, inaczej: A × 0 → {A,B}

stan ω może być osiągnięty gdy dla pewnego stanu nie przewidziano przejścia dla którejś z liter z alfabetu wejściowego

• ∑_d0={0,1}

alfabet wejściowy nie ulega zmianie

• s_d0=α
• A_d0={γ,αγ,βγ,αβγ}

akceptujące są stany w których występuje γ odpowiadająca akceptującemu stanowi C

DAS

Ostatni etap polega na usunięciu stanów, których nie można osiągnąć za pomocą żadnej sekwencji liter z alfabetu wejściowego. Należy w tym celu zacząć od stanu początkowego s_d0 i oznaczać kolejne stany do których istnieje ścieżka. Ostatecznie otrzymujemy:

• S_d={α,αβ,βγ,ω}
• ∑_d={0,1}
• s_d=α
• A_d={βγ}

Bibliografia

• Szablon:Cytuj książkę