Дискретно-стохастические модели (P-схемы)

Вероятностный автомат(англ, probabilistic automat) (ВА) - это дискретный потактный преобразователь информации с памятью, функционирова­ние которого в каждом такте зависит только от состояния памяти нем и может быть описано статистически.

Схемы вероятностных автоматов (Р-схем)применяются:

- в проектировании дискретных систем, проявляющих статистически закономерное случайное пове­дение;

- в определении алгоритмических возможностей систем;

- в обосновании границ целесообразности их использования;

- в решении задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям.

Математическое понятие Р-автоматаформируется на понятиях, введенныхдля F-автомата.

Пусть множество G, элемен­тами которого являются всевозможные пары где x_i и z_s — элементы входного подмножества X и подмножества состояний Z соответственно . Если существуют две такие функции и , то с их помощью осуществляются отображения и , то говорят, что (1) определяет конечный автомат детерминиро­ванного типа.

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

Таблица 1

При этом , (2) где b_kj — вероятности перехода автомат в состояние z_k и выдаче на выходе сигнала y_j, если автомат был в состоянии z._S, и на его вход в момент времени поступил сигнал х_i. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G.

Обозначим множество этих таблиц через В. Тогда четверка элементов называ­ется вероятностным автоматом (Р-автоматом).

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

Таблица 2

Элементы из Y	•••	y1	y2	•••	YJ-1	y J
	•••	q1	q2	•••	q J-1	q J
Элементы из Z	•••	z1	z2	•••	zK-1	zK
	•••	n1	n2	•••	n K-1	n K

При этом и (4)— вероятности перехода Р-автомата в состояние z_k и выдачи выходного сигнала y_k при условии, что Р-автомат находился в состоянии z_S и на его вход поступил входной сигнал x_t.

Если для всех k и j имеет место соотношение (5), то такой автомат называется вероятностным автоматом Мили.Представленное тре­бование означает выполнение условия независимости распределе­ний для нового состояния Р-автоматаи его выходного сигнала.

Вероятностный автомат Мура.Пусть выходной сигнал Р-автоматазави­сит лишь от того состояния, в котором находится автомат в данном такте работы, каждый элемент выходного подмножества Y индуцирует распределение вероятностей выходов, имеющее следующий вид:

Таблица 3

Здесь ,(6)где S_i, — вероятность появления сигнала на выходе y_i при условии, что Р-автоматнаходился в состоянии z_k.

Частным случаем Р-автомата являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Такой автомат называется Y-детерминированным вероятност­ным автоматом.

Если состояние Р-автомата определяется детерменированно, то такой автомат называется Z-детерминированным вероятност­ным автоматом.

Аналогично, Z-детерминированным вероятност­ным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.