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 stanów, wynikowy DAS może mieć do stanów, wykładniczo więcej, co czyni proces niepraktycznym dla dużych NAS.

Opis metodyEdytuj

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 konstrukcjaEdytuj

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ładEdytuj

Dany jest NAS:

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


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


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

BibliografiaEdytuj