Determinizacja automatu skończonego: Różnice pomiędzy wersjami

'''Determinizacją automatu skończonego''' nazywamy proces tworzenia [[deterministyczny automat skończony|deterministycznego automatu skończonego]] z [[niedeterministyczny automat skończony|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 ==

* S_n={A,B,C}

* s_n=A

* A_n={C}

Odpowiadający mu [[Deterministyczny automat skończony|DAS]] będzie miał 2^|S_n|=2³=8 stanów:

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:

{{stub}}

 

[[de:Potenzmengenkonstruktion]]