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 stanów, wynikowy DAS może mieć do stanów, wykładniczo więcej, co czyni proces niepraktycznym dla dużych NAS.
Opis metody Determinizacja niedeterministycznego automatu skończonego polega na konstrukcji deterministycznego automatu który będzie symulował działanie Automat po każdym przejściu pamięta zbiór wszystkich stanów, które 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 stają się więc zbiory stanów
Formalna konstrukcja Niech nad alfabetem będzie automatem niedeterministycznym o zbiorze stanów funkcji przejść stanie początkowym i zbiorze stanów akceptujących Wtedy automat zdefiniowany w następujący sposób:
jest deterministyczny i akceptuje ten sam język co
Przykład right|NAS Dany jest NAS: Sn={A,B,C} ∑n={0,1} sn=A An={C}
right|DAS Odpowiadający mu DAS będzie miał 2|Sn|=23=8 stanów: Sd0={α,β,γ,αβ,αγ,βγ,αβγ,ω} α 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 sd0=α Ad0={γ,αγ,βγ,αβγ} akceptujące są stany w których występuje γ odpowiadająca akceptującemu stanowi C
right|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 sd0 i oznaczać kolejne stany do których istnieje ścieżka. Ostatecznie otrzymujemy: Sd={α,αβ,βγ,ω} ∑d={0,1} sd=α Ad={βγ}
Bibliografia
Kategoria:Teoria automatów