right|DAS 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
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 sd0 i oznaczać kolejne stany do których istnieje ścieżka. Ostatecznie otrzymujemy: Sd={α,αβ,βγ,ω} ∑d={0,1} sd=α Ad={βγ}
Bibliografia
Kategoria:Teoria automatów