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

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

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

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

Определение [ править ]

Вероятностный автомат может быть определен как расширение недетерминированного конечного автомата вместе с двумя вероятностями: вероятностью того, что происходит переход в конкретное состояние, и с начальным состоянием, замененным стохастическим вектором, дающим вероятность нахождения автомата в заданном состоянии. начальное состояние.${\ 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 \delta (q,a,q^{\prime })=0}$${\displaystyle q^{\prime }\notin \delta (q,a)}$

${\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 \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{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 ,(p-1)}$

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

Обобщения [ править ]

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

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

Заметки [ править ]

Ссылки [ править ]

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