Gewichteter Automat

Der gewichtete Automat ist ein mathematisches Konzept aus der theoretischen Informatik, speziell aus der Automatentheorie. Es ist eine Verallgemeinerung des Automaten. Während die Transitionen eines (deterministischen oder nichtdeterministischen) Automaten mit Buchstaben des zugrundeliegenden Alphabets beschriftet sind, wird den Transitionen eines gewichteten Automaten zusätzlich ein bestimmtes Gewicht zugeordnet. Es kann zum Beispiel als Aufwand interpretiert werden der betrieben werden muss, um vom einen Zustand zum anderen zu gelangen, während eine bestimmte Aktion durchgeführt wird.

Mathematische Definition

Sei ${\displaystyle \mathbb {K} =(K,+,\cdot ,0,1)}$ ein Halbring, ${\displaystyle Q}$ eine nichtleere Menge und ${\displaystyle \Sigma }$ ein Alphabet. Ein Fünftupel ${\displaystyle {\mathcal {A}}=(Q,\Sigma ,\delta ,\lambda ,\theta )}$ heißt gewichteter Automat mit Kosten (Gewichten) in ${\displaystyle \mathbb {K} }$, falls: ${\displaystyle \delta \colon Q\times \Sigma \times Q\rightarrow \mathbb {K} }$, ${\displaystyle \lambda \colon Q\rightarrow \mathbb {K} }$ und ${\displaystyle \theta \colon Q\rightarrow \mathbb {K} }$. ${\displaystyle \delta }$ ist dann die Transitionsfunktion, ${\displaystyle \lambda }$ sind die Einstiegsgewichte und ${\displaystyle \theta }$ die Ausstiegsgewichte.

Ein Pfad in einem gewichteten Automaten ist eine Folge ${\displaystyle (q_{0},a_{1},q_{1},a_{2},...,a_{n},q_{n})\ }$, wobei ${\displaystyle q_{0},...,q_{n}\in Q}$ Zustände und ${\displaystyle a_{1},...,a_{n}\in \Sigma }$ Buchstaben sind. Die Beschriftung dieses Pfades lautet ${\displaystyle a_{1}a_{2}...a_{n}\ }$. Das Gewicht eines solchen Pfades beträgt ${\displaystyle \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 für ein Wort ${\displaystyle w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}}$ das Gewicht zu berechnen, addiert der Automat die Gewichte aller Pfade mit der Beschriftung ${\displaystyle w}$ zusammen. Die von einem Automaten berechnete Funktion ${\displaystyle |{\mathcal {A}}|\colon \Sigma ^{*}\rightarrow \mathbb {K} }$ heißt auch formale Potenzreihe.

Beispiele

Ein Halbring, der bei gewichteten Automaten oft betrachtet wird ist der tropische Halbring, ${\displaystyle \mathbb {T} =(R\cup \infty ,min,+,\infty ,0)}$ wobei ${\displaystyle \infty }$ das neutrale Element bezüglich der Minimumsbildung und 0 das neutrale Element bezüglich der Addition ist. Bei Automaten über diesem Halbring ist Gewicht eines Wortes ${\displaystyle w}$ das Minimum der Gewichte aller Pfade mit der Beschriftung ${\displaystyle w}$. Ein sehr konkretes Beispiel für einen gewichteten Automaten über ${\displaystyle \mathbb {T} }$ ist

zum Beispiel betragen hier die Einstiegskosten für ${\displaystyle q_{1}}$ 1. Die Transitionskosten von ${\displaystyle q_{1}}$ nach ${\displaystyle q_{2}}$ betragen für a ${\displaystyle \infty }$ und für b 2. Da im tropischen Halbring die erste Operation ("Addition") die Minimumbildung ist und die zweite Operation die Addition, ist für ein gegebenes Wort das Gewicht gerade das Minimum aller Summen entlang von Pfaden die mit diesem Wort beschriftet sind. Für das Wort aba ist zum Beispiel der Pfad ${\displaystyle q_{1},a,q_{1},b,q_{2},a,q_{2}\ }$ der einzige Pfad mit endlichem Gewicht und damit der minimale Pfad. Also sind die Kosten von aba genau 10.

Ein weiterer Halbring ist der Boolesche Halbring, ${\displaystyle \mathbb {B} =(\{0,1\},\vee ,\wedge ,0,1)}$ mit den beiden logischen Operationen "und" und "oder" und den neutralen Elementen "0"(=falsch) bezüglich "oder" und "1"(=wahr) bezüglich "und". Jeder endliche Automat ${\displaystyle {\mathcal {A}}}$ (nicht gewichtet) hat genau einen korrespondierenden Booleschen Automat ${\displaystyle {\mathcal {B}}}$. Die Transitionen von ${\displaystyle {\mathcal {A}}}$ koennen dabei in Transitionen in ${\displaystyle {\mathcal {B}}}$ übersetzt werden die das Gewicht "1" haben. Alle anderen Transitionen in ${\displaystyle {\mathcal {B}}}$ haben dann das Gewicht "0". In ${\displaystyle {\mathcal {B}}}$ haben dann genau die Pfade das Gewicht "1", die in ${\displaystyle {\mathcal {A}}}$ existieren. Daher sind gewichtete Automaten ein allgemeineres Konzept als endliche Automaten.