Determinizacja automatu skończonego: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
+przyklad |
fix |
||
Linia 22: | Linia 22: | ||
[[Image:NASdoDASetap3.svg|right|DAS]] |
[[Image: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: |
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>={α,βγ} |
* S<sub>d</sub>={α,βγ,ω} |
||
* ∑<sub>d</sub>={0,1} |
* ∑<sub>d</sub>={0,1} |
||
* s<sub>d</sub>=α |
* s<sub>d</sub>=α |
Wersja z 18:44, 23 lip 2007
Determinizacją automatu skończonego nazywamy proces tworzenia deterministycznego automatu skończonego z 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
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={βγ}