Autòmat finit acíclic determinista

Un autòmat finit acíclic determinista és un tipus d'autòmat finit (en anglès deterministic acyclic finite state automaton, DAFSA) és una estructura de dades que representa un conjunt de cadenes de caràcters i permet operacions de cerca i qüestions sobre si una cadena donada pertany al conjunt en un temps proporcional a la seva longitud. Existeixen algorismes per construir i mantenir aquest tipus d'autòmats mantenint-los de mida mínima.

Un DAFSA és un cas especial d'autòmat finit reconeixedor que pren la forma de graf acíclic dirigit amb un sol vèrtex font (un vèrtex sense cap entrada), on cada aresta del graf està etiquetada amb una lletra o símbol, i per cada vèrtex te almenys una aresta per cada símbol o lletra possible. Les cadenes representades per un DAFSA estan formades pels símbols en els camins al graf des del vèrtex font fins a qualsevol vèrtex destí (un vèrtex sense cap sortida). De fet, un autòmat finit determinista és acíclic si i només si reconeix un conjunt finit de cadenes.

Comparació amb tries

Les cadenes "TAP", "TAPS", "TOP" i "TOPS" emmagatzemat en un trie (esquerra) i en un DAFSA (dreta). (EOW significa final de paraula (End Of Word))

Com que un DAFSA permet que a un vèrtex s'hi arribi per diversos camins, un DAFSA pot fer servir menys vèrtexs que una estructura de tipus trie. Si s'agafem les paraules "tap", "taps", "top" i "tops" com a exemple, es veu que un trie per aquestes quatre paraules necessita de 12 vèrtexs, un per cada una de les cadenes formades com a prefix de les paraules. Un DAFSA pot representar les mateixes paraules amb només 6 vèrtexs.

La diferència principal entre un DAFSA i un trie és l'eliminació de la redundància a l'hora d'emmagatzemar prefixos i infixos.

Com que en un DAFSA els nodes terminal s'hi poden arribar per diversos camins, un DAFSA no pot emmagatzemar informació auxiliar relativa a cada un dels camins.