Autòmat finit acíclic determinista
From Wikipedia, the free encyclopedia
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.[1]
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.[2]