Дискретно-стохастическая модель. Вероятностный автомат

Сущность дискретизации во времени здесь остается такой же, как и в конечных детерминированных автоматах. Стохастичность же проявляется в них по-разному. В частности, вероятностный автомат (или – автомат от англ. probabilistik automat) можно определить как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит от состояния памяти в нем и может быть описано статистически [6].

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

Пусть Ф-множество всевозможных пар (), где - элемент выходного подмножества . Потребуем, чтобы любой элемент множества индуцировал на множестве Ф некоторый закон распределения вероятностей следующего вида:

––––––––––––––––––––––––––––––––––––––––––––––––––––––––

элементы из Ф! ()! () …! ()! ()

–––––––––––––––!–––––––––––––––––––––––––––––––––––––––––

()! ! …! !

,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

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

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

Элементы из … …

()... …

Элементы из … …

() … …

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

Если для всех k и j имеет место соотношение , то такой автомат называется вероятностным автоматом Мили. При этом выполняется условие независимости распределений для нового состояния P-автомата и его выходного сигнала.

Если выходной сигнал автомата зависит лишь от того состояния, в котором находится автомат в данном такте работы, то каждый элемент подмножества состояний X индуцирует на каждый элемент подмножества Y распределение вероятностей выходов, имеющее следующий вид:

Элементы из Y … …

… …

Здесь , где -вероятность появления выходного сигнала при условии, что P-автомат находился в состоянии .

Если для всех и имеет место соотношение , то такой автомат называется вероятностным автоматом Мура.

Если выходной сигнал – автомата определяется детерминировано, то такой автомат называется Y – детерминированным вероятностным автоматом. Аналогично, X – детерминированным вероятностным автоматом называется – автомат, у которого выбор нового состояния является детерминированным.

Задание – детерминированного – автомата эквивалентно заданию некоторой дискретной марковской цепи с конечным множеством состояний.

Дата добавления: 2014-12-27