Probabilistic automaton

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. 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; 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 (DFA) has exactly one next state, and a nondeterministic finite automaton (NFA) has a set of next states. A probabilistic automaton (PA) instead has a weighted set (or vector) 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 $(Q,\Sigma ,\delta ,q_{0},F)$, together with two probabilities: the probability $P$ of a particular state transition taking place, and with the initial state $q_{0}$ 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 of states $Q$
• a finite set of input symbols $\Sigma$
• a transition function $\delta :Q\times \Sigma \to \wp (Q)$
• a set of states $F$ distinguished as accepting (or final) states $F\subseteq Q$.

Here, $\wp (Q)$ denotes the power set of $Q$.

By use of currying, the transition function $\delta :Q\times \Sigma \to \wp (Q)$ of a non-deterministic finite automaton can be written as a membership function

$\delta :Q\times \Sigma \times Q\to \{0,1\}$

so that $\delta (q,a,q^{\prime })=1$ if $q^{\prime }\in \delta (q,a)$ and $0$ otherwise. The curried transition function can be understood to be a matrix with matrix entries

$\left[\theta _{a}\right]_{qq^{\prime }}=\delta (q,a,q^{\prime })$

The matrix $\theta _{a}$ is then a square matrix, whose entries are zero or one, indicating whether a transition $q{\stackrel {a}{\rightarrow }}q^{\prime }$ 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 $P_{a}$, for each symbol a in the alphabet $\Sigma$ so that the probability of a transition is given by

$\left[P_{a}\right]_{qq^{\prime }}$

A state change from some state to any state must occur with probability one, of course, and so one must have

$\sum _{q^{\prime }}\left[P_{a}\right]_{qq^{\prime }}=1$

for all input letters $a$ and internal states $q$. The initial state of a probabilistic automaton is given by a row vector $v$, whose components are the probabilities of the individual initial states $q$, that add to 1:

$\sum _{q}\left[v\right]_{q}=1$

The transition matrix acts on the right, so that the state of the probabilistic automaton, after consuming the input string $abc$, would be

$vP_{a}P_{b}P_{c}$

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.

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 $(Q,\Sigma ,P,v,F)$. Автомат Рабина — это автомат, для которого начальное распределение $v$ is a coordinate vector; that is, has zero for all but one entries, and the remaining entry being one.

Стохастические языки

Совокупность языков, распознаваемых вероятностными автоматами, называется стохастическими языками . Они включают обычные языки в качестве подмножества.

Позволять $F=Q_{\text{accept}}\subseteq Q$ — множество «принимающих» или «конечных» состояний автомата. Злоупотребляя обозначениями, $Q_{\text{accept}}$ также можно понимать как вектор-столбец, который является функцией принадлежности для $Q_{\text{accept}}$; то есть он имеет 1 в местах, соответствующих элементам в $Q_{\text{accept}}$, и ноль в противном случае. Этот вектор можно сжать с вероятностью внутреннего состояния, чтобы сформировать скаляр . Тогда язык, распознаваемый конкретным автоматом, определяется как

$L_{\eta }=\{s\in \Sigma ^{*}\vert vP_{s}Q_{\text{accept}}>\eta \}$

где $\Sigma ^{*}$ это набор всех строк в алфавите $\Sigma$ (так что * — звезда Клини ). Язык зависит от значения точки отсечения $\eta$, обычно находится в диапазоне $0\leq \eta <1$.

Язык называется η -стохастическим тогда и только тогда, когда существует некоторый PA, распознающий этот язык, при фиксированном $\eta$. Язык называется стохастическим тогда и только тогда, когда существует некоторая $0\leq \eta <1$ для чего $L_{\eta }$ является η -стохастической.

Точка разреза называется изолированной точкой разреза тогда и только тогда, когда существует $\delta >0$ такой, что

$\vert vP(s)Q_{\text{accept}}-\eta \vert \geq \delta$

для всех $s\in \Sigma ^{*}$

Характеристики

Каждый регулярный язык стохастичен, и, более того, каждый регулярный язык η -стохастичен. Слабое обратное состоит в том, что каждый 0-стохастический язык регулярен; однако общее обратное неверно: существуют стохастические языки, которые не являются регулярными.

Всякий п -стохастический язык стохастичен для некоторого $0<\eta <1$.

Любой стохастический язык представим автоматом Рабина.

Если $\eta$ является изолированной точкой отсечения, то $L_{\eta }$ это обычный язык.

p- адические языки

языки p -адические дают пример стохастического языка, который не является регулярным, а также показывают, что число стохастических языков несчетно. p - адический язык определяется как набор строк

$L_{\eta }(p)=\{n_{1}n_{2}n_{3}\ldots \vert 0\leq n_{k}<p{\text{ and }}0.n_{1}n_{2}n_{3}\ldots >\eta \}$

в письмах $0,1,2,\ldots ,(p-1)$.

То есть p -адический язык — это просто набор действительных чисел в [0, 1], записанных в системе счисления p , таких, что они больше, чем $\eta$. Несложно показать, что все p -адические языки стохастические. В частности, это означает, что число стохастических языков неисчислимо. p когда -адический язык регулярен тогда и только тогда, $\eta$ является рациональным.

Обобщения

Вероятностный автомат имеет геометрическую интерпретацию: под вектором состояния можно понимать точку, живущую на грани стандартного симплекса , противоположной ортогональному углу. Матрицы перехода образуют моноид , действующий на точку. Это можно обобщить, если точка находится в некотором общем топологическом пространстве , а матрицы перехода выбираются из набора операторов, действующих в топологическом пространстве, образуя таким образом полуавтомат . Когда точка пересечения соответствующим образом обобщена, получается топологический автомат .

Примером такого обобщения является квантовый конечный автомат ; здесь состояние автомата представлено точкой в ​​комплексном проективном пространстве , а матрицы переходов представляют собой фиксированный набор, выбранный из унитарной группы . Под точкой отсечения понимается предел максимального значения квантового угла .

Ссылки

• Саломаа, Арто (1969). «Конечные недетерминированные и вероятностные автоматы». Теория автоматов . Оксфорд: Пергамон Пресс .