Definition
The probabilistic automaton may be defined as an extension of a non-deterministic finite automaton, together with two probabilities: the probability of a particular state transition taking place, and with the initial state replaced by a stochastic vector giving the probability of the automaton being in a given initial state.
For the ordinary non-deterministic finite automaton, one has
- a finite set of states
- a finite set of input symbols
- a transition function
- a set of states distinguished as accepting (or final) states .
Here, denotes the power set of .
By use of currying, the transition function of a non-deterministic finite automaton can be written as a membership function
so that if and if . The curried transition function can be understood to be a matrix with matrix entries
The matrix is then a square matrix, whose entries are zero or one, indicating whether a transition is allowed by the NFA. Such a transition matrix is always defined for a non-deterministic finite automaton.
The probabilistic automaton replaces this matrix by a stochastic matrix, so that the probability of a transition is given by
A state change from some state to any state must occur with probability one, of course, and so one must have
for all input letters and internal states . The initial state of a probabilistic automaton is given by a row vector, whose components add to unity:
The transition matrix acts on the right, so that the state of the probabilistic automaton, after consuming the input string, would be
In particular, the state of a probabilistic automaton is always a stochastic vector, since the product of any two stochastic matrices is a stochastic matrix, and the product of a stochastic vector and a stochastic matrix is again a stochastic vector. This vector is sometimes called the distribution of states, emphasizing that it is a discrete probability distribution.
Formally, the definition of a probabilistic automaton does not require the mechanics of the non-deterministic automaton, which may be dispensed with. Formally, a probabilistic automaton PA is defined as the tuple . A Rabin automaton is one for which the initial distribution is a coordinate vector; that is, has zero for all but one entries, and the remaining entry being one.
Read more about this topic: Probabilistic Automaton
Famous quotes containing the word definition:
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (1772–1834)
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)