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 $\Sigma$ będzie automatem niedeterministycznym o zbiorze stanów $Q_{N}$, funkcji przejść $f_{N}:\Sigma \rightarrow {\mathcal {P}}(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}={\mathcal {P}}(Q_{N})$
• $f_{D}:Q_{D}\times \Sigma \ni (S,a)\rightarrow \bigcup _{s\in S}f_{N}(s,a)\in Q_{D}$
• $F_{D}=\{S\in Q_{D}:S\cap F_{N}\neq \emptyset \}$

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

• John E. Hopcroft: Wprowadzenie do teorii automatów, języków i obliczeń. Warszawa: Wydawnictwo Naukowe PWN, 2005, s. 59. ISBN 83-01-14502-1.