In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 Applied science, practical discipli ...
, 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 tr ...
; 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 happe ...
and of a
subshift of finite type In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state machine ...
. 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
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 a ...
.
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 tr ...
(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). 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 tr ...
, 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
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of states
* a finite set of
input symbol
In formal language theory, an alphabet is a non-empty set of symbols/glyphs, typically thought of as representing letters, characters, or digits but among other possibilities the "symbols" could also be a set of phonemes (sound units). Alphabets in ...
s
* 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 po ...
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 that ...
, 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-dimensiona ...
; 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
Scalar may refer to:
*Scalar (mathematics), an element of a field, which is used to define a vector space, usually the field of real numbers
* Scalar (physics), a physical quantity that can be described by a single element of a number field such ...
. The language recognized by a specific automaton is then defined as
:
where
is the set of all
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
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 syll ...
(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 c ...
). 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
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
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 points ...
, while the transition matrices are chosen from a collection of operators acting on the topological space, thus forming a
semiautomaton In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output. It consists of a set ''Q'' of states, a set Σ called the input alphabet, and a function ''T'': ''Q'' × Σ → ''Q'' ...
. 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 a ...
.
An example of such a generalization is the
quantum finite 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 a ...
; 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 a ...
, 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 is an ...
. The cut-point is understood as a limit on the maximum value of the
quantum angle
In physics, a quantum (plural quanta) is the minimum amount of any physical entity (physical property) involved in an interaction. The fundamental notion that a physical property can be "quantized" is referred to as "the hypothesis of quantizati ...
.
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 cor ...
, year = 1969 , chapter = Finite nondeterministic and probabilistic automata
Finite automata
Probabilistic models