Т а б л и ц а 3.5

Отмеченная таблица переходов асинхронного автомата Мура с тремя состояниями (z₀, z₁, z₂), тремя входными (x₁, x₂, x₃) и тремя выходными (₁y, y₂, y₃) сигналами

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

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

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

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

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

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

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

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

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

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

Элементы из Ф (xi, zs)

… …

(z1, y1) b11

(z1, y2) b12

… …

(zK, yJ-1) bK(J-1)

(zK, yJ) bKJ

При этом , где b_kj – вероятность перехода автомата в состояние z_k и появления на выходе сигнала y_j, если он был в состоянии z_s, и на его вход в этот момент времени поступил сигнал x_i. Число таких распределений, представленных в виде таблиц, равно числу элементов множества 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

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

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

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

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

… …

y1 s1

y2 s2

… …

yK-1 sI-1

yK sI

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

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

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

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

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

Дата добавления: 2014-11-20