Determinizacja automatu skończonego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

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

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

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