The set of languages recognized by probabilistic automata are called stochastic languages. They include the regular languages 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 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 (so that * is the Kleene star). 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
Read more about this topic: Probabilistic Automaton
Famous quotes containing the word languages:
“No doubt, to a man of sense, travel offers advantages. As many languages as he has, as many friends, as many arts and trades, so many times is he a man. A foreign country is a point of comparison, wherefrom to judge his own.”
—Ralph Waldo Emerson (1803–1882)