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

В отличие от детерминированных автоматов, где функции переходов и выходов взаимнооднозначны:

в вероятностных автоматах эти функции носят вероятностный характер и задают вероятности появления состояния в момент времени t + 1и вероятности появления выходной буквы. В вероятностном автомате действует механизм случайности: состояния автомата и выходные буквы появляются случайным образом:

Эта формула задает условную вероятность того, что в момент времени t + 1 автомат перейдет в состояние a(t+l), если в момент времени t автомат был в состоянии a(t), и поступила x(t).

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

1)Вероятностный автомат Мили:

P[a(t+ 1)y(t)/a(t),x(t)] = P[a(t+ 1)/a(t), x(t)]*P[y(t)/a(t) , x(t)].

Функция перехода функция выхода

2) Вероятностный автомат Мура:

P[a(t+ 1)y(t)/a(t),x(t)] = P[a(t+ 1)/a(t), x(t)]*P[y(t)/a(t)].

3) Y - детерминированный автомат: функция переходов вероятностная, функция выходов детерминированная:

4) А - детерминированный автомат. Автомат, у которого функция переходов детерминированная: