Determinizacja automatu skończonego


Determinizacja automatu skończonego w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do 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 {\displaystyle n} stanów, wynikowy DAS może mieć do 2 n {\displaystyle 2^{n}} stanów, wykładniczo więcej, co czyni proces niepraktycznym dla dużych NAS.

Spis treści

Opis metody | edytuj kod

Determinizacja niedeterministycznego automatu skończonego N {\displaystyle N} polega na konstrukcji deterministycznego automatu D , {\displaystyle D,} który będzie symulował działanie N . {\displaystyle N.} Automat D {\displaystyle D} po każdym przejściu pamięta zbiór wszystkich stanów, które N {\displaystyle 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 {\displaystyle D} stają się więc zbiory stanów N . {\displaystyle N.}

Formalna konstrukcja | edytuj kod

Niech N = ( Q N , f N , q 0 , F N ) {\displaystyle N=(Q_{N},f_{N},q_{0},F_{N})} nad alfabetem Σ {\displaystyle \Sigma } będzie automatem niedeterministycznym o zbiorze stanów Q N , {\displaystyle Q_{N},} funkcji przejść f N : Σ P ( Q N ) , {\displaystyle f_{N}:\Sigma \to {\mathcal {P}}(Q_{N}),} stanie początkowym q 0 {\displaystyle q_{0}} i zbiorze stanów akceptujących F N . {\displaystyle F_{N}.} Wtedy automat D = ( Q D , f D , { q 0 } , F D ) {\displaystyle D=(Q_{D},f_{D},\{q_{0}\},F_{D})} zdefiniowany w następujący sposób:

  • Q D = P ( Q N ) {\displaystyle Q_{D}={\mathcal {P}}(Q_{N})}
  • f D : Q D × Σ ( S , a ) s S f N ( s , a ) Q D {\displaystyle f_{D}:Q_{D}\times \Sigma \ni (S,a)\to \bigcup _{s\in S}f_{N}(s,a)\in Q_{D}}
  • F D = { S Q D : S F N } {\displaystyle F_{D}=\{S\in Q_{D}:S\cap F_{N}\neq \emptyset \}}

jest deterministyczny i akceptuje ten sam język co N . {\displaystyle N.}

Przykład | edytuj kod

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

Bibliografia | edytuj kod

Na podstawie artykułu: "Determinizacja automatu skończonego" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy