Вероятностный автомат

Эта статья может быть слишком технической для понимания большинства читателей . Пожалуйста, помогите улучшить ее, чтобы сделать ее понятной для неспециалистов , не удаляя технические детали. ( Январь 2021 ) ( Узнайте, как и когда удалять это сообщение )

В математике и информатике вероятностный автомат ( PA ) является обобщением недетерминированного конечного автомата ; он включает вероятность заданного перехода в функцию перехода , превращая ее в матрицу перехода . ^{[1] [2]} Таким образом, вероятностный автомат также обобщает понятия цепи Маркова и подсдвига конечного типа . Языки, распознаваемые вероятностными автоматами, называются стохастическими языками ; они включают регулярные языки как подмножество. Число стохастических языков неисчислимо .

Концепция была введена Майклом О. Рабином в 1963 году; ^[2] определенный особый случай иногда называют автоматом Рабина (не путать с подклассом ω-автоматов, также называемых автоматами Рабина). В последние годы был сформулирован вариант в терминах квантовых вероятностей, квантовый конечный автомат .

Для заданного начального состояния и входного символа детерминированный конечный автомат (DFA) имеет ровно одно следующее состояние, а недетерминированный конечный автомат (NFA) имеет набор следующих состояний. Вероятностный автомат (PA) вместо этого имеет взвешенный набор (или вектор ) следующих состояний, где веса должны быть в сумме равны 1 и, следовательно, могут интерпретироваться как вероятности (делая его стохастическим вектором ). Понятия состояний и принятия также должны быть изменены, чтобы отразить введение этих весов. Состояние машины как заданного шага теперь также должно быть представлено стохастическим вектором состояний, и состояние принимается, если его общая вероятность находиться в состоянии принятия превышает некоторое отсечение.

PA в некотором смысле является промежуточным шагом от детерминированного к недетерминированному, поскольку он допускает набор следующих состояний, но с ограничениями на их веса. Однако это несколько вводит в заблуждение, поскольку PA использует понятие действительных чисел для определения весов, которое отсутствует в определении как DFA, так и NFA. Эта дополнительная свобода позволяет им определять языки, которые не являются регулярными, такие как p-адические языки с иррациональными параметрами. Таким образом, PA более мощны, чем DFA и NFA (которые, как известно, одинаково мощны).

Вероятностный автомат можно определить как расширение недетерминированного конечного автомата вместе с двумя вероятностями: вероятностью осуществления определенного перехода состояния и заменой начального состояния стохастическим вектором, дающим вероятность нахождения автомата в заданном начальном состоянии.${\displaystyle (Q,\Sigma,\delta,q_{0},F)}$${\displaystyle P}$${\displaystyle q_{0}}$

Для обычного недетерминированного конечного автомата имеем

• конечный набор состояний${\displaystyle Q}$
• конечный набор входных символов ${\displaystyle \Сигма}$
• функция перехода${\displaystyle \delta :Q\times \Sigma \to \wp (Q)}$
• набор состояний, выделенных как принимающие (или конечные ) состояния .${\displaystyle F}$ ${\displaystyle F\subseteq Q}$

Здесь обозначает множество степеней .${\displaystyle \wp (Q)}$${\displaystyle Q}$

Используя каррирование , функцию перехода недетерминированного конечного автомата можно записать как функцию принадлежности${\displaystyle \delta :Q\times \Sigma \to \wp (Q)}$

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

так что если и в противном случае. Каррированную функцию перехода можно понимать как матрицу с матричными элементами${\displaystyle \delta (q,a,q^{\prime})=1}$${\displaystyle q^{\prime }\in \delta (q,a)}$${\displaystyle 0}$

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

Матрица тогда является квадратной матрицей, элементы которой равны нулю или единице, что указывает, разрешен ли переход NFA. Такая матрица перехода всегда определена для недетерминированного конечного автомата.${\displaystyle \theta _{a}}$${\displaystyle q{\stackrel {a}{\rightarrow }}q^{\prime }}$

Вероятностный автомат заменяет эти матрицы семейством правых стохастических матриц для каждого символа a в алфавите, так что вероятность перехода определяется как${\displaystyle P_{a}}$${\displaystyle \Сигма}$

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

Изменение состояния из некоторого состояния в любое состояние должно происходить с вероятностью единица, конечно, и поэтому необходимо иметь

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

для всех входных букв и внутренних состояний . Начальное состояние вероятностного автомата задается вектором -строкой , компоненты которого являются вероятностями отдельных начальных состояний , которые в сумме дают 1:${\displaystyle а}$${\displaystyle д}$ ${\displaystyle v}$${\displaystyle д}$

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

Матрица перехода действует справа, так что состояние вероятностного автомата после потребления входной строки будет${\displaystyle abc}$

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

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

Формально определение вероятностного автомата не требует механики недетерминированного автомата, без которой можно обойтись. Формально вероятностный автомат PA определяется как кортеж . Автомат Рабина — это автомат, для которого начальное распределение является вектором координат ; то есть имеет ноль для всех записей, кроме одной, а оставшаяся запись равна единице.${\displaystyle (Q,\Sigma ,P,v,F)}$${\displaystyle v}$

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

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

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

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

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

Говорят, что точка разделения является изолированной точкой разделения тогда и только тогда, когда существует такое , что${\displaystyle \дельта >0}$

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

для всех${\displaystyle s\in \Сигма ^{*}}$

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

Каждый η -стохастический язык является стохастическим, для некоторых .${\displaystyle 0<\эта <1}$

Каждый стохастический язык может быть представлен автоматом Рабина.

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

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

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

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

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

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

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

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