Determinizacja automatu skończonego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj]

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[edytuj]

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[edytuj]

NAS

Dany jest NAS:

  • Sn={A,B,C}
  • n={0,1}
  • sn=A
  • An={C}


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


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[edytuj]