Determinizacja automatu skończonego – 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, co automat wejściowy. Jakkolwiek, gdy NAS ma stanów, wynikowy DAS może mieć do stanów, wykładniczo więcej, co czyni proces niepraktycznym dla dużych NAS.
Opis metody Determinizacja niedeterministycznego automatu skończonego polega na konstrukcji deterministycznego automatu który będzie symulował działanie Automat po każdym przejściu pamięta zbiór wszystkich stanów, które mógłby osiągnąć w danym kroku. Jeżeli po zakończeniu działania ten zbiór zawiera jakikolwiek stan akceptujący, przeczytane słowo jest akceptowane. Stanami automatu stają się więc zbiory stanów
Formalna konstrukcja Niech nad alfabetem będzie automatem niedeterministycznym o zbiorze stanów funkcji przejść stanie początkowym i zbiorze stanów akceptujących Wtedy automat zdefiniowany w następujący sposób:
jest deterministyczny i akceptuje ten sam język co
Przykład right|NAS Dany jest NAS: Sn={A,B,C} ∑n={0,1} sn=A An={C}