Weighted automaton

Builds on Semiring Alphabet String Nondeterministic finite automaton

Definition

Let $(K, \oplus, \otimes, 0, 1)$ be a semiring and let $\Sigma$ be an alphabet. A weighted automaton over $K$ and $\Sigma$ is a tuple $A = (Q, \lambda, \mu, \gamma)$ where:

$Q$ is a finite set of states;
$\lambda \colon Q \to K$ gives the initial weights;
$\mu \colon \Sigma \to K^{Q \times Q}$ gives, for each letter $a$ , a $Q \times Q$ matrix $\mu(a)$ of transition weights;
$\gamma \colon Q \to K$ gives the final weights.

Extend $\mu$ to strings by $\mu(a_1 \cdots a_n) = \mu(a_1) \cdots \mu(a_n)$ , a product of matrices over $K$ , with $\mu(\varepsilon)$ the identity matrix. The weight of $w \in \Sigma^*$ is $f_A(w) = \bigoplus_{p, q \in Q} \lambda(p) \otimes \mu(w)_{p, q} \otimes \gamma(q).$ The map $f_A \colon \Sigma^* \to K$ is a formal power series with coefficients in $K$ and noncommuting variables in $\Sigma$ .

Remarks

Equivalently, $f_A(w)$ is the sum over all paths labelled $w$ of the product of the initial weight, the transition weights and the final weight along the path. Example: over the semiring $(\N, +, \cdot)$ with $\Sigma = \set{a, b}$ , take $Q = \set{1, 2}$ , $\lambda = (1, 0)$ , $\gamma = (0, 1)$ , $\mu(a) = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ and $\mu(b)$ the identity matrix. Since $\mu(a)^k = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}$ , the weight of $w$ is $\mu(w)_{1,2}$ , the number of $a$ 's in $w$ . Non-example: a device with infinitely many states, such as one that tracks the exact count of $a$ 's minus $b$ 's, fails clause 1. Over the Boolean semiring $(\set{0, 1}, \lor, \land)$ , a weighted automaton is an NFA, possibly with several initial states, and its weight function is the indicator function of its language. Commutativity of $\otimes$ is not required.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Alphabet concept
Nondeterministic finite automaton concept
Semiring concept
String concept
Weighted automaton definition

Tag	`NG9P5YKNPC`
URI	`m2://NG9P5YKNPC`
Kind	definition
Writing	W0 stub
MSC	68Q45, 16Y60
Defines	Weighted automaton
Uses	Semiring, Alphabet, String, Nondeterministic finite automaton
Changed	3 November 2026

Weighted automaton

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here