Deterministischer azyklischer endlicher Automat
Datenstruktur aus der theoretischen Informatik / aus Wikipedia, der freien encyclopedia
Ein deterministischer azyklischer endlicher Automat (DAEA; englisch deterministic acyclic finite state automaton (DAFSA)[1] oder directed acyclic word graph, DAWG) ist in der theoretischen Informatik eine Datenstruktur, die eine Menge von Zeichenketten darstellt und eine Abfrageoperation ermöglicht, die prüft, ob eine gegebene Zeichenkette in einer Zeit, die proportional zu ihrer Länge ist, zu dieser Menge gehört. Es gibt Algorithmen, um solche Automaten zu konstruieren und zu verwalten,[1] wobei diese minimal gehalten werden.
Ein DAEA ist ein Spezialfall eines endlichen Automaten, der die Form eines gerichteten azyklischen Graphen mit einem einzigen Quellknoten (einem Knoten ohne eingehende Kanten) hat, bei dem jede Kante des Graphen mit einem Buchstaben oder Symbol beschriftet ist und bei dem jeder Knoten höchstens eine ausgehende Kante für jeden möglichen Buchstaben oder jedes mögliche Symbol hat. Die durch die DAEA dargestellten Zeichenketten werden durch die Symbole auf den Pfaden im Graphen vom Quellknoten zu einem beliebigen Senkenknoten (ein Knoten ohne ausgehende Kanten) gebildet. Ein deterministischer endlicher Automat ist dann und nur dann azyklisch, wenn er eine endliche Menge von Zeichenketten erkennt.[1]