Tak jednak nie jest, i każdy NFA można za pomocą prostej procedury przeprowadzić w DFA.
Przykład Weźmy NFA rozpoznające język słów nad alfabetem binarnym, których czwartym od końca znakiem jest 1:
– jedynym niedeterministycznym przejściem jest przejście ze stanu po przeczytaniu jedynki, albo w albo w
Stan startowy to stanem akceptującym jest
Możemy uruchomić ten automat na słowie
Choć możemy też uruchomić go tak, żeby nie zaakceptował słowa:
Konwersja NFA do DFA Pomyślmy jak można emulować NFA na deterministycznym komputerze. Pierwsza myśl to wypróbowanie wszystkich możliwych ciągów stanów i sprawdzenie czy nie ma wśród nich jakiegoś stanu akceptującego. Metoda ta, acz poprawna, generuje jednak potencjalnie wykładniczo wiele ścieżek w porównaniu do długości słowa.
Nie musimy jednak pamiętać wszystkich ścieżek.