Determinizacja automatu skończonego

background image

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

background image

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

background image

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


Wyszukiwarka

Podobne podstrony:
209 Komputerowa analiza automatów skończonych
4 2 RG Automaty skonczone id 38 Nieznany (2)
4 3 RG Przeksztalcenia automatow skonczonych
Automaty skonczone handout
ćw4 Automaty skończone, gramatyki, wyrażenia regularne
Sprawozdanie z WDI Automat skończony, Biotechnologia, Fizyka, Labolatorium
Automat skończony
208 komputerowa realizacja automatow skonczonych, Politechnika Wrocławska - Materiały, logika uklado
implementacja automatu skonczonego pelniacego funkcje automatu niedeterministycznego, Politechnika W
208 komputerowa realizacja automatow skonczonych 3id 28837
209 komputerowa analiza automatow skonczonych
implementacja automatu skonczonego pelniacego funkcje automatu niedeterministycznego012, Politechnik
208 komputerowa realizacja automatow skonczonych 2, Politechnika Wrocławska - Materiały, logika ukla
sprawozdanie synteza automatów skończonych
buchalski,logika układow cyfrowych, ZASTOSOWANIE JĘZYKA WYRAŻEŃ NATURALNYCH DO SYNTEZY I ANALIZY AUT
Automaty skonczone handout

więcej podobnych podstron