Wat is Deterministic Finite Automata?
Deterministic Finite Automata (of DFA) zijn eindige-toestandsmachines die tekenreeksen accepteren of afwijzen door ze door een reeks te halen die uniek wordt bepaald door elke tekenreeks.
De term “deterministisch” verwijst naar het feit dat elke tekenreeks, en dus elke toestandsreeks, uniek is. In een DFA wordt een tekenreeks van symbolen door een DFA-automaat geanalyseerd, en elk ingevoerd symbool gaat naar de volgende toestand die kan worden bepaald.
Deze automaten worden eindig genoemd omdat er een beperkt aantal mogelijke toestanden is die kunnen worden bereikt. Een eindige automaat wordt alleen deterministisch genoemd als hij aan beide voorwaarden kan voldoen. DFA’s verschillen van niet-deterministische automaten doordat de laatste in staat zijn naar meer dan één toestand tegelijk over te gaan en in meerdere toestanden tegelijk actief te zijn.
In de praktijk bestaan DFA’s uit vijf componenten (en ze worden vaak aangeduid met een set van vijf symbolen, bekend als een 5-tuple). Deze componenten zijn:
- Een eindig aantal toestanden
- Een verzameling symbolen bekend als het alfabet, ook eindig in aantal
- Een functie die de overgang tussen toestanden voor elk symbool bedient
- Een aanvankelijke begintoestand waarin de eerste invoer wordt gegeven of verwerkt
- Een eindtoestand of -toestanden, bekend als accepterende toestanden.
Zie Sisense in actie:
Explore Dashboard
Hoe kan ik Deterministic Finite Automata gebruiken?
Hoewel ze oorspronkelijk gemaakt zijn als abstracte wiskundige modellen, zijn DFA’s vandaag de dag wijdverbreid in zowel computer- als data science. Eindige automaten worden door de meeste compilers van computertaal gebruikt om te helpen bij het parseren en het voorbereiden van code voor daadwerkelijk gebruik. Bovendien worden ze uitgebreid gebruikt in taalverwerkingssystemen, ook in natuurlijke taalverwerking, om programma’s te helpen begrijpen hoe ze moeten reageren op unieke en gevarieerde inputs.
DFA’s zijn, vanwege hun onvermogen om meerdere toestanden tegelijk actief te bewonen, ook essentieel in alles van wachtwoordherkenningsalgoritmen (om te bepalen of de invoer van een gebruiker juist of onjuist is) tot filteralgoritmen en zelfs in tekstverwerkingstoepassingen. In de datawetenschap kunnen deterministische eindige automaten worden gebruikt als sorteerhulpmiddelen bij het bouwen van datawarehouses en andere opslagsystemen.
Door gegevens bij binnenkomst te ontleden en de juiste plaats ervan te bepalen, kan een DFA een groot deel van het sorteren automatiseren en wel aanzienlijk sneller dan wanneer de taak handmatig wordt uitgevoerd. In combinatie met een niet-deterministisch eindig automatisme (NFA) kunnen data warehouses ook nagaan of gegevens op meer dan één plaats thuishoren. DFA en NFA kunnen afzonderlijk worden gebruikt om een veel bredere en effectieve oplossing te creëren.
Zie Sisense in actieTerug naar Woordenlijst