In
mathematics and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, the probabilistic automaton (PA) is a generalization of the
nondeterministic finite automaton
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state t ...
; it includes the probability of a given transition into the
transition function, turning it into a
transition matrix.
[ Thus, the probabilistic automaton also generalizes the concepts of a ]Markov chain
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...
and of a subshift of finite type. The languages
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...
recognized by probabilistic automata are called stochastic languages; these include the regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s as a subset. The number of stochastic languages is uncountable
In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal numb ...
.
The concept was introduced by Michael O. Rabin
Michael Oser Rabin ( he, מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israeli mathematician and computer scientist and a recipient of the Turing Award.
Biography Early life and education
Rabin was born in 1931 in ...
in 1963; a certain special case is sometimes known as the Rabin automaton (not to be confused with the subclass of ω-automata also referred to as Rabin automata). In recent years, a variant has been formulated in terms of quantum probabilities, the quantum finite automaton.
Informal Description
For a given initial state and input character, a deterministic finite automaton
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...
(DFA) has exactly one next state, and a nondeterministic finite automaton
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state t ...
(NFA) has a set of next states. A probabilistic automaton (PA) instead has a weighted set (or vector
Vector most often refers to:
*Euclidean vector, a quantity with a magnitude and a direction
*Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism
Vector may also refer to:
Mathematic ...
) of next states, where the weights must sum to 1 and therefore can be interpreted as probabilities (making it a stochastic vector
In mathematics and statistics, a probability vector or stochastic vector is a vector space, vector with non-negative entries that add up to one.
The positions (indices) of a probability vector represent the possible outcomes of a discrete random ...
). The notions states and acceptance must also be modified to reflect the introduction of these weights. The state of the machine as a given step must now also be represented by a stochastic vector of states, and a state accepted if its total probability of being in an acceptance state exceeds some cut-off.
A PA is in some sense a half-way step from deterministic to non-deterministic, as it allows a set of next states but with restrictions on their weights. However, this is somewhat misleading, as the PA utilizes the notion of the real numbers to define the weights, which is absent in the definition of both DFAs and NFAs. This additional freedom enables them to decide languages that are not regular, such as the p-adic languages with irrational parameters. As such, PAs are more powerful than both DFAs and NFAs (which are famously equally powerful).
Formal Definition
The probabilistic automaton may be defined as an extension of a nondeterministic finite automaton
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state t ...
, together with two probabilities: the probability of a particular state transition taking place, and with the initial state replaced by a stochastic vector
In mathematics and statistics, a probability vector or stochastic vector is a vector space, vector with non-negative entries that add up to one.
The positions (indices) of a probability vector represent the possible outcomes of a discrete random ...
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
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is ...
of .
By use of currying
In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. For example, currying a function f tha ...
, the transition function of a non-deterministic finite automaton can be written as a membership function
In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\ ...
:
so that if and otherwise. 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 these matrices by a family of right stochastic matrices , for each symbol a in the alphabet 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
In linear algebra, a column vector with m elements is an m \times 1 matrix consisting of a single column of m entries, for example,
\boldsymbol = \begin x_1 \\ x_2 \\ \vdots \\ x_m \end.
Similarly, a row vector is a 1 \times n matrix for some n, c ...
, whose components are the probabilities of the individual initial states , that add to 1:
:
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
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
.
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
In linear algebra, a coordinate vector is a representation of a vector as an ordered list of numbers (a tuple) that describes the vector in terms of a particular ordered basis. An easy example may be a position such as (5, 2, 1) in a 3-dimensio ...
; that is, has zero for all but one entries, and the remaining entry being one.
Stochastic languages
The set of languages
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...
recognized by probabilistic automata are called stochastic languages. They include the regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s as a subset.
Let be the set of "accepting" or "final" states of the automaton. By abuse of notation, can also be understood to be the column vector that is the membership function
In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\ ...
for ; that is, it has a 1 at the places corresponding to elements in , and a zero otherwise. This vector may be contracted with the internal state probability, to form a scalar. The language recognized by a specific automaton is then defined as
:
where is the set of all strings in the alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a s ...
(so that * is the Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid ...
). The language depends on the value of the cut-point , normally taken to be in the range .
A language is called ''η''-stochastic if and only if there exists some PA that recognizes the language, for fixed . A language is called stochastic if and only if there is some for which is ''η''-stochastic.
A cut-point is said to be an isolated cut-point if and only if there exists a such that
:
for all
Properties
Every regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
is stochastic, and more strongly, every regular language is ''η''-stochastic. A weak converse is that every 0-stochastic language is regular; however, the general converse does not hold: there are stochastic languages that are not regular.
Every ''η''-stochastic language is stochastic, for some .
Every stochastic language is representable by a Rabin automaton.
If is an isolated cut-point, then is a regular language.
''p''-adic languages
The ''p''-adic languages provide an example of a stochastic language that is not regular, and also show that the number of stochastic languages is uncountable. A ''p''-adic language is defined as the set of strings
:
in the letters .
That is, a ''p''-adic language is merely the set of real numbers in , 1 written in base-''p'', such that they are greater than . It is straightforward to show that all ''p''-adic languages are stochastic. In particular, this implies that the number of stochastic languages is uncountable. A ''p''-adic language is regular if and only if is rational.
Generalizations
The probabilistic automaton has a geometric interpretation: the state vector can be understood to be a point that lives on the face of the standard simplex
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension ...
, opposite to the orthogonal corner. The transition matrices form a monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ...
, acting on the point. This may be generalized by having the point be from some general topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called po ...
, while the transition matrices are chosen from a collection of operators acting on the topological space, thus forming a semiautomaton. When the cut-point is suitably generalized, one has a topological automaton
In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of au ...
.
An example of such a generalization is the quantum finite automaton; here, the automaton state is represented by a point in complex projective space
In mathematics, complex projective space is the projective space with respect to the field of complex numbers. By analogy, whereas the points of a real projective space label the lines through the origin of a real Euclidean space, the points of ...
, while the transition matrices are a fixed set chosen from the unitary group
In mathematics, the unitary group of degree ''n'', denoted U(''n''), is the group of unitary matrices, with the group operation of matrix multiplication. The unitary group is a subgroup of the general linear group . Hyperorthogonal group i ...
. The cut-point is understood as a limit on the maximum value of the quantum angle.
Notes
References
*{{ cite book , last1 = Salomaa , first1 = Arto , author-link = Arto Salomaa, title = Theory of Automata , location = Oxford , publisher = Pergamon Press
Pergamon Press was an Oxford-based publishing house, founded by Paul Rosbaud and Robert Maxwell, that published scientific and medical books and journals. Originally called Butterworth-Springer, it is now an imprint of Elsevier.
History
The c ...
, year = 1969 , chapter = Finite nondeterministic and probabilistic automata
Finite automata
Probabilistic models