Vad är deterministiska finita automater?
Deterministiska finita automater (eller DFA) är maskiner med ändliga tillstånd som accepterar eller förkastar teckensträngar genom att analysera dem genom en sekvens som är unikt bestämd av varje sträng.
Tecknet ”deterministisk” hänvisar till det faktum att varje sträng, och därmed varje tillståndssekvens, är unik. I en DFA analyseras en teckensträng genom en DFA-automat, och varje ingångssymbol flyttas till nästa tillstånd som kan bestämmas.
Dessa maskiner kallas ändliga eftersom det finns ett begränsat antal möjliga tillstånd som kan nås. En ändlig automat kallas deterministisk endast om den kan uppfylla båda villkoren. DFA:er skiljer sig från icke-deterministiska automater genom att de senare kan övergå till mer än ett tillstånd i taget och vara aktiva i flera tillstånd samtidigt.
I praktiken består DFA:er av fem komponenter (och de betecknas ofta med en uppsättning med fem symboler som kallas 5-tupel). Dessa komponenter omfattar följande:
- Ett ändligt antal tillstånd
- En uppsättning symboler som kallas alfabetet, som också är ändligt antal
- En funktion som sköter övergången mellan tillstånden för varje symbol
- Ett initialt starttillstånd där den första inmatningen ges eller bearbetas
- Ett eller flera sluttillstånd, så kallade accepterande tillstånd.
Se Sisense i aktion:
Explore Dashboard
Hur kan jag använda deterministiska finita automater?
Och även om de ursprungligen skapades som abstrakta matematiska modeller, har DFA:s idag blivit utbredda inom både data- och datavetenskap. Finita automater används av de flesta datorspråkskompilatorer för att hjälpa till med att analysera och förbereda kod för faktisk användning. Dessutom används de i stor utsträckning i språkbearbetningssystem, bland annat för behandling av naturliga språk, för att hjälpa program att förstå hur de ska reagera på unika och varierande inmatningar.
DDFA:er, på grund av deras oförmåga att aktivt bebo flera tillstånd samtidigt, är också viktiga i allt från algoritmer för lösenordsigenkänning (för att avgöra om en användares inmatning är korrekt eller inkorrekt) till filtreringsalgoritmer och till och med i tillämpningar för textbearbetning. Inom datavetenskap kan grundläggande deterministiska finita automater användas som sorteringsverktyg när man bygger datalager och andra lagringssystem.
Genom att analysera data när de anländer och bestämma deras rätta plats kan en DFA automatisera en stor del av sorteringen och göra det betydligt snabbare än att utföra uppgiften manuellt. I kombination med en icke-deterministisk finitautomat (Non-deterministic Finite Automaton eller NFA) kan datalager också fastställa om data hör hemma på mer än en plats. DFA och NFA kan användas separat för att skapa en mycket bredare och effektiv lösning.
Se Sisense i praktikenTillbaka till ordlistan