Determinizacja automatu
skończonego
Z Wikipedii, wolnej encyklopedii
Determinizacją automatu skończonego nazywamy 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 (zbiór słów),
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.
Przykład
Dany jest NAS:
S
n
={A,B,C}
∑
n
={0,1}
s
n
=A
A
n
={C}
Determinizacja automatu skończonego – Wikipedia...
http://pl.wikipedia.org/wiki/Determinizacja_automa...
1 z 3
29.05.2011 18:20
Odpowiadający mu DAS
będzie miał 2
|S
n
|
=2
3
=8
stanów:
S
d0
={α,β,γ,αβ,αγ,βγ,αβγ,ω}
α 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
s
d0
=α
A
d0
={γ,αγ,βγ,αβγ}
akceptujące są stany w których występuje γ odpowiadająca akceptującemu
stanowi C
Determinizacja automatu skończonego – Wikipedia...
http://pl.wikipedia.org/wiki/Determinizacja_automa...
2 z 3
29.05.2011 18:20
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
d0
i
oznaczać kolejne stany do których istnieje
ścieżka. Ostatecznie otrzymujemy:
S
d
={α,αβ,βγ,ω}
∑
d
={0,1}
s
d
=α
A
d
={βγ}
Źródło „http://pl.wikipedia.org
/wiki/Determinizacja_automatu_sko
%C5%84czonego”
Kategoria: Teoria automatów
Tę stronę ostatnio zmodyfikowano 01:58, 31 gru 2010. Tekst udostępniany
na licencji Creative Commons: uznanie autorstwa, na tych samych
warunkach, z możliwością obowiązywania dodatkowych ograniczeń. Zobacz
szczegółowe informacje o warunkach korzystania.
Determinizacja automatu skończonego – Wikipedia...
http://pl.wikipedia.org/wiki/Determinizacja_automa...
3 z 3
29.05.2011 18:20