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:
“The less sophisticated of my forbears avoided foreigners at all costs, for the very good reason that, in their circles, speaking in tongues was commonly a prelude to snake handling. The more tolerant among us regarded foreign languages as a kind of speech impediment that could be overcome by willpower.”
—Barbara Ehrenreich (b. 1941)