Determinizacja automatu skończonego: Różnice pomiędzy wersjami

m
drobne techniczne - patrz WP:CHECK, WP:SK
m (drobne techniczne - patrz WP:CHECK, WP:SK)
'''Determinizacją automatu skończonego''' nazywamy proces tworzenia [[deterministyczny automat skończony|deterministycznego automatu skończonego]] z [[niedeterministyczny automat skończony|niedeterministycznego automatu skończonego]]. Transformacja taka jest zawsze możliwa i otrzymany w jej procesie automat akceptuje dokładnie ten sam język (zbiór słów), co automat wejściowy.
 
== Przykład ==
[[ImagePlik:NASdoDASetap1.svg|right|NAS]]
Dany jest [[Niedeterministyczny_automat_skończonyNiedeterministyczny automat skończony|NAS]]:
* S<sub>n</sub>={A,B,C}
* &sum;<sub>n</sub>={0,1}
* s<sub>n</sub>=A
* A<sub>n</sub>={C}
{{-}}
<br clear="all"/>
 
[[ImagePlik:NASdoDASetap2.svg|right|DAS]]
Odpowiadający mu [[Deterministyczny automat skończony|DAS]] będzie miał 2<sup>|S<sub>n</sub>|</sup>=2<sup>3</sup>=8 stanów:
* S<sub>d0</sub>={&alpha;α,&beta;β,&gamma;γ,&alpha;&beta;αβ,&alpha;&gamma;αγ,&beta;&gamma;βγ,&alpha;&beta;&gamma;αβγ,&omega;ω}
:&alpha; α odpowiada stanowi A, &beta;β stanowi B, a &gamma;γ stanowi C
: stan &alpha;&beta;αβ będzie osiągany na przykład, gdy ze stanu A dla 0 na wejściu odpowiada jednocześnie przejście A&rarr;AA→A i A&rarr;BA→B, inaczej: A &times;× 0 &rarr; {A,B}
: stan &omega;ω może być osiągnięty gdy dla pewnego stanu nie przewidziano przejścia dla którejś z liter z alfabetu wejściowego
* &sum;<sub>d0</sub>={0,1}
: alfabet wejściowy nie ulega zmianie
* s<sub>d0</sub>=&alpha;α
* A<sub>d0</sub>={&gamma;γ,&alpha;&gamma;αγ,&beta;&gamma;βγ,&alpha;&beta;&gamma;αβγ}
: akceptujące są stany w których występuje &gamma;γ odpowiadająca akceptującemu stanowi C
{{-}}
<br clear="all"/>
 
[[ImagePlik:NASdoDASetap3.svg|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 s<sub>d0</sub> i oznaczać kolejne stany do których istnieje ścieżka. Ostatecznie otrzymujemy:
* S<sub>d</sub>={&alpha;α,&alpha;&beta;αβ,&beta;&gamma;βγ,&omega;ω}
* &sum;<sub>d</sub>={0,1}
* s<sub>d</sub>=&alpha;α
* A<sub>d</sub>={&beta;&gamma;βγ}
 
<br clear="all"/>
[[Kategoria:Teoria automatów]]
{{stub}}
 
[[Kategoria:Teoria automatów]]
 
[[de:Potenzmengenkonstruktion]]