 | This article may be too technical for most readers to understand. (January 2021) |
In mathematics and computer science, the probabilistic automaton (PA) is a generalization of the nondeterministic finite automaton; it includes the probability of a given transition into the transition function, turning it into a transition matrix.[1][2] Thus, the probabilistic automaton also generalizes the concepts of a Markov chain and of a subshift of finite type. The languages recognized by probabilistic automata are called stochastic languages; these include the regular languages as a subset. The number of stochastic languages is uncountable.
The concept was introduced by Michael O. Rabin in 1963;[2] 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.
- ^ Paz, Azaria (2014). Introduction to probabilistic automata. ISBN 9781483244655. OCLC 1027002902.
- ^ a b Michael O. Rabin (1963). "Probabilistic Automata". Information and Control. 6 (3): 230–245. doi:10.1016/s0019-9958(63)90290-0.