Weighted automaton
In theoretical computer science and formal language theory, a weighted automaton or weighted finite-state machine is a generalization of a finite-state machine in which the edges have weights, for example real numbers or integers.
Finite-state machines are only capable of answering decision problems; they take as input a string and produce a Boolean output, i.e. either "accept" or "reject".
In contrast, weighted automata produce a quantitative output, for example a count of how many answers are possible on a given input string, or a probability of how likely the input string is according to a probability distribution.
[2] They are one of the simplest studied models of quantitative automata.
[1]: Fig.1 The definition of a weighted automaton is generally given over an arbitrary semiring
, an abstract set with an addition operation
The automaton consists of a finite set of states, a finite input alphabet of characters
and edges which are labeled with both a character in
The weighted automaton thus defines a function from
[2] Weighted automata generalize deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs), which correspond to weighted automata over the Boolean semiring, where addition is logical disjunction and multiplication is logical conjunction.
In the DFA case, there is only one accepting path for any input string, so disjunction is not applied.
When the weights are real numbers and the outgoing weights for each state add to one, weighted automata can be considered a probabilistic model and are also known as probabilistic automata.
These machines define a probability distribution over all strings, and are related to other probabilistic models such as Markov decision processes and Markov chains.
Weighted automata have applications in natural language processing where they are used to assign weights to words and sentences,[3][2]: 571–596 as well as in image compression.
[2]: 453–480 They were first introduced by Marcel-Paul Schützenberger in his 1961 paper On the definition of a family of automata.
[4] Since their introduction, many extensions have been proposed, for example nested weighted automata,[5] cost register automata,[6] and weighted finite-state transducers.
[7] Researchers have studied weighted automata from the perspective of learning a machine from its input-output behavior[8] (see computational learning theory) and studying decidability questions.
[9] A commutative semiring (or rig) is a set R equipped with two distinguished elements
and addition and multiplication operations
is commutative and associative with identity
is a finite path in the graph, where the concatenation of the character labels equals
is a set of transitions, weighted automata allow multiple transitions (or paths) on a single input string.
Therefore a weighted automaton can be considered analogous to a nondeterministic finite automaton (NFA).
As is the case with NFAs, restrictions of weighted automata are considered that correspond to the concepts of deterministic finite automaton and unambiguous finite automaton (deterministic weighted automata and unambiguous weighted automata, respectively).
First, a preliminary definition: the underlying NFA of
is an NFA formed by removing all transitions with weight
A weighted automaton is deterministic if the underlying NFA is deterministic and unambiguous if the underlying NFA is unambiguous.
Every deterministic weighted automaton is unambiguous.
In both the deterministic and unambiguous cases, there is always at most one accepting path, so the
operation is never applied and can be omitted from the definition.
