Determinizacja automatu skończonego: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m r2.7.1) (Robot dodał pt:Conversão AFN AFD |
m +dopracować |
||
Linia 1:
{{dopracować|Brakuje opisu metody, choćby ogólnego. Sam przykład jest niewystarczający i raczej niezbyt szczegółowy.}}
'''Determinizacją automatu skończonego''' nazywamy proces tworzenia [[deterministyczny automat skończony|deterministycznego automatu skończonego]] (DAS) z [[niedeterministyczny automat skończony|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.
| |||