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

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

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

Неофициальное описание

Для данного начального состояния и входного символа детерминированный конечный автомат (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 \ Sigma}$
• функция перехода ${\ displaystyle \ delta: Q \ times \ Sigma \ to \ wp (Q)}$
• набор состояний, определяемых как принимающие (или конечные ) состояния .${\ displaystyle F}$ ${\ Displaystyle F \ substeq 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 \ дельта (д, а, д ^ {\ простое}) = 1}$${\ Displaystyle д ^ {\ простое} \ в \ дельта (д, а)}$${\ 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 \ Sigma}$

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

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

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

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

${\ Displaystyle \ сумма _ {д} \ влево [v \ вправо] _ {д} = 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}} \ substeq Q}$${\ displaystyle Q _ {\ text {accept}}}$${\ displaystyle Q _ {\ text {accept}}}$${\ displaystyle Q _ {\ text {accept}}}$

${\ displaystyle L _ {\ eta} = \ {s \ in \ Sigma ^ {*} \ vert vP_ {s} Q _ {\ text {accept}}> \ eta \}}$

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

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

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

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

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

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

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

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

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

Если - изолированная точка разреза, то - регулярный язык. ${\ displaystyle \ eta}$${\ displaystyle L _ {\ eta}}$

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

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

${\ displaystyle 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 \}}$

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

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

Обобщения

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

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

Примечания

использованная литература

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