Возможные приложения.

Если для всех к и I имеет место соотношение гкв1к то такой Р-автомат называется вероятностным автоматом Мура. Понятие Р-авто матов Мили и Мура введено по аналогии с детерминированным Р-автоматом, задаваемым Р=

Ху У у (ру фу. Частным случаем Р-автомата, задаваемого как Р= <^, X, У, В являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Если выходной сигнал Р-автомата определяется детерминированно, то такой автомат называется У-детерминированным вероятностным автоматом. Аналогично, Z-дemepмuнupoβaнным вероятностным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.

Пример 2.4. Рассмотрим У-детерминированньй Р-автомат, который задан таблицей переходов (табл. 2.6) и таблицей выходов:

В этих таблицах рц — вероятность перехода Р-автомата из состояния г, в состо

яние 2}. При этом, как и ранее,

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

Таблица 2.6

к. При этом

Для описания У-детерминированного Р-автомата необходимо задать начальное распределение вероятностей вида

Здесь <1К — вероятность того, что в начале работы Р-автомат находится в состоянии

Будем считать, что до начала работы (до нулевого такта времени) Р-автомат всегда находится в состоянии z0 и в нулевой такт времени меняет состояние в соответствии с распределением D. Дальнейшая смена состояний P-автомата определяется матрицей переходов Рг. Информацию о начальном состоянии Р-автомата удобно ввести в матрицу Р* увеличив ее размерность до (К+ 1)х (К+1). При этом первая строка такой матрицы, сопоставляемая состоянию г0, будет иметь вид (0, </,, а2, ... ..." dg), а первый столбец будет нулевым.

Описанный У-де терминированный Р-автомат можно задать в виде ориентированного графа, вершины которого сопоставляются состояниям автомата, а дуги — возможным переходам из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода pij, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями.

Пример U. Пусть задан У-детерминированный Р-автомат

На рис. 2.5 показан граф переходов этого автомата. Требуется оценить суммарные финальные вероятности пребывания этого Р-автомата в состояниях гг и

При использовании аналитического подхода можно записать известные соотношения из теории марковских цепей и получить систему уравнений для определения финальных вероятностей. При этом начальное состояние 20 можно не учитывать, так как начальное распределение не оказывает влияния на значения финальных вероятностей. Тогда имеем

где Ск — финальная вероятность пребывания Р-автомата в состоянии г*. Получаем систему уравнений

Добавим к этим уравнениям условие нормировки с, + с2 + с3Ч-с4" 1. Тогда, решая систему уравнений, получим с, "5/23, са-8/23, с3" 5/23, с4" 5/23. Таким образом, са3 = 13ДЗ=0,5652. Другими словами, при бесконечной работе заданного в этом примере У-детерминированного Р- автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы, равной 0,5652.

Подобные Р-авто маты могут использоваться как генераторы марковских последовательностей, которые необходимы при построении и реализации процессов функционирования систем 5 или воздействий внешней среды Е.

Для оценки различных характеристик исследуемых систем, представляемых в виде Р-схем, кроме рассмотренного случая аналитических моделей можно применять и имитационные модели, реализуемые, например, методом статистического моделирования.

Граф вероятностного автомата

Рис. 2.5. Граф вероятностного автомата

 
< Пред   СОДЕРЖАНИЕ     След >