Autômato finito determinístico acíclico
De Wikipedia, a enciclopédia encyclopedia
Em ciência da computação, um autômato finito determinístico acíclico (AFDA),[1] também chamado de grafo orientado acíclico de palavras (GOAP; apesar desse nome também se referir a uma estrutura de dados relacionada que funciona como um índice de sufixo[2]) é uma estrutura de dados que representa um conjunto de cadeias de caracteres, e permite uma operação de consulta que testa se uma dada cadeia pertence ao conjunto em tempo proporcional ao seu comprimento. Algoritmos existem para criar e manter tais autômatos, enquanto os mantêm mínimo.
Um AFDA é um caso especial de uma máquina de estados finitos que toma a forma de um grafo acíclico orientado com um único vértice fonte (um vértice que nenhuma aresta o têm como destino), em que cada aresta do grafo é rotulada por uma letra ou um símbolo, e em que cada vértice tem no máximo uma aresta que o têm como origem por símbolo. As sequências de caracteres representados pelo AFDA são formada pelos símbolos nos caminhos do grafo a partir do vértice fonte para o vértice sumidouro (ou poço) (um vértice que nenhuma aresta o têm como origem). De fato, um autômato finito determinístico é acíclico se, e somente se reconhece um conjunto finito de cadeias de caracteres.[1]