Determinizacja automatu skończonego

Determinizacją automatu skończonego nazywamy 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 (zbiór słów), 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.

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={βγ}