deterministisk og ikke- deterministisk Finite Automata finnes to typer konseptuelle "maskiner " laget for å sjekke om et gitt streng av symboler adlyder visse regler - hvis det er akseptabelt som en melding i noen språk eller kode . Automatikken leser et enkelt symbol i en tid , og alltid finnes i en spesiell "tilstand. " Hver stat en automater kan være i har et sett med regler for å reagere på det neste symbolet for å bli lest - det kan endre til en annen bestemt tilstand eller forbli den samme . Dersom det etter en hel streng er lest , har automater inngått en av et sett av akseptable " endelige stater," strengen er grammatisk akseptabelt innenfor språket automater er testing for . Instruksjoner
en

Undersøk automater regler . Disse inkluderer : . Alle automater er mulige tilstander , sitt sett av endelige tilstander og effekter av alle mulige symbol på hver stat
2

Sjekk å se om noen av automater i statene har flere mulige reaksjoner på et bestemt symbol . Hvis noen gjør det, er det automater ikke- deterministisk - en NDFA . For eksempel, hvis en automata sin opprinnelige tilstand kan reagere på symbolet " A" enten ved å flytte til en annen stat eller ved å forbli det samme, er det en NDFA . En NDFA returnerer et positivt resultat hvis det er noen måte å komme til en endelig tilstand ved hjelp av en gitt streng .
3

Husk at en DFA finnes for hver NDFA . Fordi en NDFA returnere et positivt resultat for en bestemt streng må ha minst en vellykket bane gjennom det i denne strengen , må der av nødvendighet være en tilsvarende DFA som vil akseptere at strengen , som kun inneholder reglene for enkelt bane som ble brukt. Her er et veldig enkelt eksempel : Anta at du har en NDFA med en endelig tilstand kalt S1 , som opprinnelig tilstand S0 reagerer på symbolet " A" enten ved å endre til S1 eller ved å forbli i S0 . Denne maskinen vil godta en streng som består ganske enkelt av " A ", fordi det er en mulig vei til S1 , og det er en tilsvarende DFA der "A" alltid endrer S1 til S0 , dispenserer med den ubrukte banen
.