# 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

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.

## Referències

* ↑ «directed acyclic word graph». [Consulta: 14 febrer 2019].
* ↑ Daciuk, Jan; Mihov, Stoyan; Watson, Bruce W.; Watson, Richard E. «Incremental Construction of Minimal Acyclic Finite-State Automata». Computational Linguistics, 26, 1, 01-03-2000, pàg. 3–16. DOI: 10.1162/089120100561601. ISSN: 0891-2017.
* ↑ Lucchesi, Claudio L.; Kowaltowski, Tomasz. Applications of Finite Automata Representing Large Vocabularies, 1992.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :