Deterministisk og Non- Deterministisk endelige automater er to typer af konceptuelle "maskiner " designet til at kontrollere, om en given streng af symboler adlyder visse regler - hvis det er acceptabelt, som en besked på nogle sprog eller kode . Den automata læser et enkelt symbol ad gangen , og altid eksisterer i en bestemt "tilstand . " Hver stat en automater kan være i har et sæt regler for at reagere på det næste symbol , der skal læses - det kan skifte til en anden bestemt stat , eller forblive den samme. Hvis der efter en hel streng er blevet læst , har automater indtastet en af ​​en række acceptable "endelige hedder," strengen er grammatisk acceptable inden for sprog automater tester for . Instruktioner
1

Undersøg automater regler. Disse omfatter : . Alle automater er mulige tilstande , dens endelige stater og virkningerne af alle mulige symbol hver stat
2

Kontroller, om nogen af ​​automater s stater har flere mulige reaktioner på en bestemt symbol . Hvis nogen gør det, automater er non- deterministisk - en NDFA . For eksempel, hvis en automater oprindelige tilstand kan reagere på symbolet " A" enten ved at flytte til en anden stat eller ved at forblive det samme, er det en NDFA . En NDFA returnerer et positivt resultat, hvis der er nogen måde at nå frem til en endelig tilstand ved hjælp af en given streng .
3

Husk, at en DFA eksisterer for hver NDFA . Fordi en NDFA returnere et positivt resultat for en bestemt streng skal have mindst én succesrig vej igennem det for denne streng , skal der nødvendigvis være et tilsvarende DFA , der vil acceptere, at strengen , der kun indeholder reglerne for det indre sti, der blev brugt. Her er et meget simpelt eksempel : Lad os antage, at du har en NDFA med en endelig tilstand kaldet S1 , hvis oprindelige tilstand S0 reagerer på symbolet " A" enten ved at skifte til S1 eller ved at forblive i S0 . Denne maskine vil acceptere en streng, der består simpelthen af "A, " fordi der er en mulig vej til S1 , og der er en tilsvarende DFA , hvor "A" altid ændrer S1 til S0 , udlevering med den ubrugte sti
.