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

Где я могу найти введение в вероятностные автоматы и что они распознают (определенные функции из слов в )? Существует ли стандартный термин для таких функций, которые распознаются вероятностными автоматами, аналогично «обычным языкам» для того, что распознают детерминированные конечные автоматы (DFA)? $[0,1]$

Я ищу что-то похожее на изучение базовых вопросов по DFA и обычным языкам, таких как свойства выразительности, замыкания и разрешимости.

Это и это не совсем то, что я ищу.

reference-request fl.formal-languages probabilistic-automata Prateek
источник

Они являются «положительными носителями»

рациональных рядов, т. Е. Языков

для

такого ряда. Хотя это не слишком хорошо. Я изучал логическое замыкание этого класса, если вам интересно: eccc.hpi-web.de/report/2013/040 .

Z

$\mathbb{Z}$

{w ∣ (r, w) > 0}

$\{w \mid (r, w) > 0\}$

r

$r$

Михаэль Кадилхак,

Ответы:

Первая статья Рабина (1963) дает основы того, что вы ищете. Класс языков, распознаваемых вероятностными автоматами (с точкой среза), называется стохастическими языками.

$P$ $\Sigma$ $f_P(w)$ $P$ $w \in \Sigma^*$ $P$ $\lambda \in [0,1)$

$L(P,\lambda) = \{ w \in \Sigma^* \mid f_P(w) > \lambda \}$

Заметьте, что распознавание с точкой отсечения можно рассматривать как распознавание с неограниченной ошибкой. В случае ограниченной ошибки (или изолированной точки отсечения) вероятностные автоматы могут распознавать все и только обычные языки.

Книга Паз (1971) и обзор Бухараева (1980) являются хорошими ссылками.

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

Абузер Якарылмаз
источник