Gewichteter Automat

Der gewichtete Automat ist ein mathematisches Konzept aus der theoretischen Informatik und der Automatentheorie. Es ist eine Verallgemeinerung des Automaten. Waehrend die Transitionen eines (deterministischen oder nichtdeterministischen) Automaten mit Buchstaben des zugrundeliegenden Alphabets beschriftet sind, wird den Transitionen eines gewichteten Automaten auch ein bestimmtes Gewicht zugeordnet. Es kann als zum Beispiel als Aufwand interpretiert werden der betrieben werden muss, um vom einen Zustand zum anderen zu gelangen, waehrend eine bestimmte Aktion durchgefuehrt wird.

Mathematische Definition

Sei $\mathbb {K} =(K,+,\cdot ,0,1)$ ein Semiring, $Q$ eine nichtleere Menge und $\Sigma$ ein Alphabet. Ein fuenftupel $\mathbb {A} =(Q,\Sigma ,\delta ,\lambda ,\theta )$ heisst gewichteter Automat, falls: $\delta :Q\times \Sigma \times Q\rightarrow \mathbb {K}$, $\lambda :Q\rightarrow \mathbb {K}$ und $\theta :Q\rightarrow \mathbb {K}$. $\delta$ ist dann die Transitionsfunktion, $\lambda$ sind die Einstiegsgewichte und $\theta$ die Ausstiegsgewichte.

Ein Pfad in einem gewichteten Automaten ist eine Folge $(q_{0},a_{1},q_{1},a_{2},...,a_{n},q_{n})$. Die Beschriftung dieses Pfades lautet $a_{1}a_{2}...a_{n}$. Das Gewicht eines solchen Pfades betraegt $\lambda (q_{0})\cdot \left(\prod _{i=1,...,n}\delta (q_{i-1},a_{i},q_{i})\right)\cdot \theta (q_{n})$. Also wird das Einstiegsgewicht mit den Gewichten der Transitionen und dem Ausstiegsgewicht multipliziert. Um fuer ein Wort $w=a_{1}a_{2}...a_{n}$ das Gewicht zu berechnen, addiert der Automat die Gewichte aller Pfade mit der Beschriftung $w$ zusammen.

Ein Semiring, der bei gewichteten Automaten oft betrachtet wird ist der tropische Semiring, $\mathbb {T} =(R\cup \infty ,min,+,\infty ,0)$ wobei $\infty$ das neutrale element bezueglich der Minimumsbildung und 0 das neutrale Element bezueglich der Addition ist. Bei Automaten ueber diesem Semiring ist Gewicht eines Wortes $w$ das minimum der Gewichte aller Pfade mit der Beschriftung $w$.