Determinizacja automatu skończonego


Determinizacja automatu skończonego  Wikipedia... http://pl.wikipedia.org/wiki/Determinizacja_automa...
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:
Sn={A,B,C}
"n={0,1}
sn=A
An={C}
1 z 3 29.05.2011 18:20
Determinizacja automatu skończonego  Wikipedia... http://pl.wikipedia.org/wiki/Determinizacja_automa...
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 AA i AB, 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
2 z 3 29.05.2011 18:20
Determinizacja automatu skończonego  Wikipedia... http://pl.wikipedia.org/wiki/Determinizacja_automa...
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={ł}
yró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.
3 z 3 29.05.2011 18:20


Wyszukiwarka

Podobne podstrony:
Niedeterministyczny automat skończony
Automat skończony
Automaty skonczone handout
4 3 RG Przeksztalcenia automatow skonczonych
4 3 RG Przeksztalcenia automatow skonczonych
WFiIS 4 Przeksztalcenia automatow skonczonych
209 Komputerowa analiza automatów skończonych
Automatyka okrętowa – praca kontrolna 2
automatyka i sterowanie wyklad
Automatyka okrętowa – praca kontrolna 4
Automatyczna Ładowarka Akumulatorów Samochodowych
Stromlaufplan Passat 52 Automatisches 4 Gang Getriebe (AG4) ab 10 2000
Uk? regulacji automatycznej
niwelatory automat 1
wyklad z analizy matematycznej dla studentow na kierunku automatyka i robotyka agh
Automatyka budynkowa wybrane systemy inteligentnych instalacji elektrycznych A Klajn
SPOSOBY AUTOMATYCZNYCH MODYFIKACJI REJESTRU

więcej podobnych podstron