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. They are one of the simplest studied models of quantitative automata.

The definition of a weighted automaton is generally given over an arbitrary semiring , an abstract set with an addition operation  and a multiplication 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  and a weight in . The weight of any path in the automaton is defined to be the product of weights along the path, and the weight of a string is the sum of the weights of all paths which are labeled with that string. The weighted automaton thus defines a function from  to .

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, as well as in image compression. They were first introduced by Marcel-Paul Schützenberger in his 1961 paper On the definition of a family of automata. Since their introduction, many extensions have been proposed, for example nested weighted automata, cost register automata, and weighted finite-state transducers. Researchers have studied weighted automata from the perspective of learning a machine from its input-output behavior (see computational learning theory) and studying decidability questions.

Definition 

A commutative semiring (or rig) is a set R equipped with two distinguished elements  and addition and multiplication operations  and  such that  is commutative and associative with identity ,  is commutative and associative with identity ,  distributes over , and 0 is an absorbing element for .

A weighted automaton over  is a tuple  where:
  is a finite set of states.
  is a finite alphabet.
  is a finite set of transitions , where  is called a character and  is called a weight.
  is an initial weight function.
  is a final weight function.

A path on input  is a finite path in the graph, where the concatenation of the character labels equals . The weight of the path  is the product () of the weights along the path, additionally multiplied by the initial and final weights . The weight of the word  is the sum () of the weights of all paths on input  (or 0 if there are no accepting paths). In this way the machine defines a function .

The underlying NFA of  is an NFA formed by removing all transitions with weight  and then erasing all of the weights on the transitions , so that the new transition set lies in . The initial states and final states are the set of states  such that  and , respectively.

Variations 

 A weighted automaton is deterministic if the underlying NFA is deterministic and unambiguous if the underlying NFA is unambiguous. In these cases, there is always exactly one accepting path, so the  operation is never applied and can be omitted from the definition.

 It is possible to extend the definition to allow epsilon transitions , where  is the empty string. In this case, one must then require that there are no cycles of epsilon transitions. This does not increase the expressiveness of weighted automata. If epsilon transitions are allowed, the initial weights and final weights can be replaced by initial and final sets of states without loss of expressiveness.

 The transition function can be given as a matrix  with entries in  for each , rather than a set of transitions. The entry of the matrix at  is the sum of all transitions labeled .

 Some authors omit the initial and final weight functions  and . Instead,  and  are replaced by a set of initial and final states. If epsilon transitions are not present, this technically decreases expressiveness as it forces  to depend only on the number of states that are both initial and final.

 Some authors restrict to specific semirings, such as  or , particularly when studying decidability results.

 The requirement that there is a zero element for  is sometimes omitted; in this case the machine defines a partial function from  to  rather than a total function.

See also

References 

Finite automata