Nieważne, co znajdowało się na początku ścieżki – nam wystarcza wiedza, jakie stany występują na dowolnej ze ścieżek po krokach.
Na początku bierzemy więc zbiór złożony jedynie ze stanu startowego emulowanego NFA, po każdym kroku zaś zbiór takich stanów że w poprzednim zbiorze był jakiś stan i możliwe jest dla aktualnie czytanego znaku przejście z w Czyli w interpretacji ścieżkowej – takich stanów że na którejś ze ścieżek krok wcześniej był stan i że jest możliwe przedłużenie tej ścieżki w tym kroku do
Słowo jest akceptowane jeśli wśród zbioru stanów po przeczytaniu całego znajduje się choć jeden stan akceptujący.
Przyjmując zbiory stanów NFA za stany DFA, każde NFA możemy emulować w pełni deterministycznie na DFA. Być może jednak liczba stanów będzie musiała wzrosnąć wykładniczo.
Przykład konwersji Weźmy podany wyżej automat rozpoznający słowa, których czwartym od końca znakiem jest jedynka. Następuje wykładnicza eksplozja liczby stanów:
Przy czym akceptujące są stany zawierające stan startowy to zaś Jedynym co choć trochę ogranicza liczbę stanów jest to, że stan jest zawsze osiągalny, więc nie musimy uwzględniać zbiorów stanów nie zawierających
Sprawdźmy tym automatem słowo