Niedeterministyczne automaty Xor (NXA) są składniowo NFA, ale mówi się, że słowo jest akceptowane przez NXA, jeśli ma nieparzystą liczbę ścieżek akceptacji (zamiast co najmniej jednej ścieżki akceptacji w przypadku NFA). Łatwo zauważyć, że dla skończonego języka regularnego LLL istnieje minimalny...
Automaty szczątkowego stanu skończonego (RFSA, zdefiniowane w [DLT02]) to NFA, które mają kilka fajnych cech wspólnych z DFA. W szczególności zawsze istnieje kanoniczny minimalny rozmiar RFSA dla każdego zwykłego języka, a język rozpoznawany przez każdy stan w RFSA jest resztkowy, podobnie jak w...
Algorytm Brzozowskiego do przekształcania DFA w równoważny DFA stanu minimalnego jest niezwykle prosty: jeśli oznacza NFA utworzony przez odwrócenie wszystkich krawędzi w DFA , czyniąc stary stan początkowy stanem akceptującym i czyniąc starym akceptowaniem stwierdza początek stanów i jeżeli...