АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Т а б л и ц а 2.5

Отмеченная таблица переходов асинхронного автомата Мура с тремя состояниями (z0, z1, z2), тремя входными (x1, x2, x3) и тремя выходными (1y, y2, y3) сигналами

xi yk
y1 y3 y2
z0 z1 z2
x1 z2 z2 z2
x2 z1 z1 z2
x3 z0 z1 z0

 

Рис. 2.5. Граф асинхронного автомата Мура

 

В таблице переходов асинхронного автомата некоторое состояние zk стоит на пересечении строки xi и столбца zs (s ¹ k), и это состояние zk обязательно должно встретиться в этой же строке в столбце zk. В графе асинхронного автомата, если в некоторое состояние имеются переходы из других состояний под действием каких-то сигналов, то в вершине zk должна быть петля, отмеченная символами тех же входных сигналов.

Понятие F –автоматаявляется математической абстракцией, удобной для описания широкого класса процессов функционирования реальных объектов, для которых характерно наличие дискретных состояний и дискретный характер работы во времени. Но широта применения не означает универсальности F –схем. Этот подход не пригоден для описания процессов в динамических системах с наличием переходных процессов, для формализации которых используются решётчатые функции и разностные уравнения, Z –преобразование и описание в пространстве состояний [14].

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

Использование Pсхем позволяет формализовать процесс функционирования дискретных систем, проявляющих статистически закономерное случайное поведение.

Вероятностный автомат (англ. Probabilistic Automata) определяется как дискретный потактовый преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нём и может быть описано статистически [8].

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

Введём математическое понятие Pавтомата, используя понятия, введённые для Fавтомата. Рассмотрим множество G, элементами которого являются всевозможные пары (xi, zs), где xi и zs – элементы входного множества X и множества состояний Z соответственно. Если существуют две такие функции φ и ψ, что с их помощью осуществляются отображения G ® Z и G ® Y, то говорят, что F = < X, Y, Z, φ, ψ, z0 > определяет автомат детерминированного типа.

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

 

Элементы из Ф (xi, zs) … … (z1, y1) b11 (z1, y2) b12 … … (zK, yJ-1) bK(J-1) (zK, yJ) bKJ

 

При этом , где bkj – вероятность перехода автомата в состояние zk и появления на выходе сигнала yj, если он был в состоянии zs, и на его вход в этот момент времени поступил сигнал xi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через B. Тогда четвёрка элементов P = < X, Y, Z, B > называется вероятностным автоматом (Pавтоматом).

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

 

Элементы из Y (xi, zs) … … y1 q1 y2 q2 … … yJ-1 qJ-1 yJ qJ
Элементы из Z (xi, zs) … … z1 z1 z2 z2 … … zK-1 zK-1 zK zK

 

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

Если для всех k и j имеет место соотношение qkzj = bkj, то такой Pавтомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния P –автомата и его выходного сигнала.

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

 

Элементы из Y zk … … y1 s1 y2 s2 … … yK-1 sI-1 yK sI

 

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

Если для всех k и i имеет место соотношение zksi = bki, то такой P –автомат называется вероятностным автоматом Мура. Понятие P –автоматовМили и Мура введено по аналогии с детерминированным F –автоматом.

Частным случаем P –автомата, задаваемого как P = < X, Y, Z, B >, являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Если выходной сигнал P –автоматаопределяется детерминированно, то такой автомат называется Yдетерминированным вероятностным автоматом. Аналогично, Zдетерминированным вероятностным автоматом называется P –автомат, у которого выбор нового состояния является детерминированным.

Способы задания работы P –автоматовтакие же, как и для F –автоматов.

В качестве примера рассмотрим Y –детерминированный вероятностный автомат, заданный таблицей переходов (табл. 2.6) и таблицей выходов (табл.2.7). До начала работы P –автоматвсегда находится в начальном состоянии z0 и в нулевой такт времени начинает изменять своё состояние в соответствии с заданным распределением.

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)