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:
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)
“One definition of man is “an intelligence served by organs.””
—Ralph Waldo Emerson (1803–1882)