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

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

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

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

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

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

Формальное определение

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

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

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

Здесь, $\wp (Q)$ обозначает мощности набор $Q$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Позволять $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 -адические языки стохастические. ^[3] В частности, это означает, что число стохастических языков неисчислимо. p когда -адический язык регулярен тогда и только тогда, $\eta$ является рациональным.

Обобщения

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

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

Примечания

^ Пас, Азария (2014). Введение в вероятностные автоматы . ISBN 9781483244655 . OCLC 1027002902 .
^ Перейти обратно: ^а ^б Майкл О. Рабин (1963). «Вероятностные автоматы» . Информация и контроль . 6 (3): 230–245. дои : 10.1016/s0019-9958(63)90290-0 .
^ Мерве Нур Чакир; Салеми, Мехвиш; Циммерманн, Карл-Хайнц (2021). «К теории стохастических автоматов». arXiv : 2103.14423 [ cs.FL ].

Ссылки

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

[1] Пас, Азария (2014). Введение в вероятностные автоматы . ISBN 9781483244655 . OCLC 1027002902 .

[:0-2] Перейти обратно: ^а ^б Майкл О. Рабин (1963). «Вероятностные автоматы» . Информация и контроль . 6 (3): 230–245. дои : 10.1016/s0019-9958(63)90290-0 .

[3] Мерве Нур Чакир; Салеми, Мехвиш; Циммерманн, Карл-Хайнц (2021). «К теории стохастических автоматов». arXiv : 2103.14423 [ cs.FL ].

[1]

[2]

[3]