deterministiska och icke - deterministiska ändliga automater finns två typer av konceptuella "maskiner" som syftar till att kontrollera om en viss sträng av symboler lyder vissa regler - om det är acceptabelt som ett meddelande i vissa språk eller kod . Den automater läser en enda symbol i taget, och alltid finns i en viss "tillstånd. " Varje stat en automater kan vara i har en uppsättning regler för att reagera på nästa symbol som ska läsas - det kan ändras till en annan viss stat , eller förblir desamma . Om det efter en hel sträng har läst , har automater in en av en uppsättning acceptabla " sluttillstånd , " strängen är grammatiskt acceptabla inom språk automater testar för . Instruktioner
1
Undersök automater s regler . Dessa inkluderar : . Samtliga automater är möjliga tillstånd , dess uppsättning slutliga tillstånd och effekterna av alla möjliga symbol på varje stat
2
Kontrollera för att se om någon av automater s stater har flera möjliga reaktioner på en särskild symbol . Om någon gör , är automater ickedeterministisk - ett NDFA . Till exempel, om en automater ursprungliga tillståndet kan reagera på symbolen " A " antingen genom att flytta till en annan stat eller genom att förbli densamma , är det en NDFA . En NDFA returnerar ett positivt resultat om det finns något sätt att nå ett slutligt tillstånd att använda en given sträng .
3
Tänk på att en DFA existerar för varje NDFA . Eftersom en NDFA returnera ett positivt resultat för en specifik sträng måste ha minst en framgångsrik väg genom det för att strängen , måste det med nödvändighet finnas en motsvarande DFA som accepterar den strängen , som endast innehåller reglerna för den enda väg som användes . Här är ett väldigt enkelt exempel : Anta att du har en NDFA med ett slutligt tillstånd som kallas S1 , vars initiala tillståndet S0 svarar på symbolen " A " antingen genom att byta till S1 eller genom att förbli i S0 . Denna maskin skulle acceptera en sträng som består helt enkelt av " A , " eftersom det finns en möjlig väg till S1 , och det finns en motsvarande DFA där " A " alltid ändrar S1 S0 , stryka den oanvända banan
. Addera
