Дискретно–детерминированные модели (F-схемы)

 

Для формализации процессов функционирования систем используют математический аппарат теории автоматов. Это раздел теоретической кибернетики, в которой изучаются математические модели, автоматы. На основе этой теории система представляется в виде черного ящика, перерабатывающего входные сигналы в выходные, и имеющего свои внутренние состояния.

Конечный автомат – ящик, у которого множество внутренних состояний и входных сигналов, а соответственно множество и выходных сигналов, являются конечными.

Абстрактный конечный автомат – автомат, представляющий собой конечную математическую схему, характеризующуюся 6 элементами:

– конечным множеством входных сигналов X (входным алфавитом);

– конечным множеством внутренних состояний Z (внутренним алфавитом);

– конечным множеством выходных сигналов Y (выходным алфавитом);

– начальным состоянием z₀, являющимся одним из состояний множества Z;

– функцией переходов j(z, x);

– функцией выходов Y(z, x).

Автомат функционирует в дискретном времени, которое представляется последовательностью тактов (интервалов времени, в течение которого состояние входных и выходных сигналов не изменяется).

Автомат, задаваемый F-схемой: F=< z, x, y, j, y, z0> , функционирует в дискретном автоматном времени, моментами которого являются такты, т. е. примыкающие друг к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния.

В каждый момент времени F-автомат находится в определенном состоянии z(t). Это состояние определяется состоянием входного сигнала в этот момент времени. Поэтому выходной сигнал представляет собой функцию y(t)=y(z(t), x(t)) от внутреннего состояния и входного сигнала в этот момент времени, а переход в следующее состояние будет определяться функцией переходов: z(t+1) = j[z(t), x(t)].

Работа конечного автомата происходит по схеме: в каждом t-м такте на вход автомата, находящегося в состоянии z(t), подается некоторый сигнал x(t), на который он реагирует переходом в (t+1)-м такте, в новое состояние z(t+1) и выдачей некоторого выходного сигнала.

Любой автомат описывается системой уравнений:

 

. (5.3)

 

Для автомата I рода (автомат Мили) система выглядит следующим образом

 

 

Для автомата II рода (автомат Мура) состояние y(t) будет определено предыдущим состоянием входного сигнала. y(t)=y(z(t)) t=0, 1, 2… Выходные сигналы определяются внутренним состоянием системы на данном такте моделирования.

По числу состояний различают конечный автомат с памятью (1) и без памяти (2).

1. Конечные автоматы с памятью используются для моделирования последовательных схем (схем с памятью), которые имеют 2 и более состояний.

2. Конечные автоматы без памяти имеют одно состояние и используются для моделирования комбинационных схем, выходные состояния которых не зависят от внутреннего состояния системы, а только от входных сигналов y(t)=y(x(t)) t=0, 1, 2…

По характеру отсчета времени автоматы делятся на синхронные и асинхронные. В синхронных F-автоматах моменты времени, в которых происходит считывание входных сигналов, определяются принудительно синхронизирующим сигналом. После очередного синхронизирующего сигнала с учетом «считанного» и в соответствии с уравнениями (3) происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение входного сигнала. То есть, реакция автомата на каждое значение входного сигнала заканчивается за один такт, длительность которого определяется интервалом между соседними синхронизирующими сигналами.

Асинхронные автоматы считывают входной сигнал непрерывно, поэтому, реагируя на длинный входной сигнал, он может несколько раз изменять состояние на выходе пока не перейдет в устойчивое состояние, которое уже не может быть изменено этим входным сигналом.

Конечный автомат может быть задан каким-либо образом, если описать элементы множеств, которые входят в описание автомата F=< z, x, y, j, y, z₀>. Необходимо выделить состояние z₀.

В настоящее время используется 3 способа задания автоматов:

– табличный;

– графический;

– матричный.

Табличный способ задания автоматов

Табличный способ основан на использование таблиц переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы – его состояниям. Первый столбец – начальное состояние z₀. На пересечении i-й строки и k-го столбца таблицы переходов помещается значение j(z_k, x_i) функции переходов, а в таблице выходов – соответствующее значение y(z_k, x_i) функции выходов.

 

Автомат Мура

	y( zk)
xi	y(z0)	y(z1)	...	y(zk)
	z0	z1	...	zk
X1	j(z0, x1)	j(z1, x1)	...	j(zk, x1)
X2	j(z0, x2)	j(z1, x2)	...	j(zk, x2)
xi	j(z0, xi)	j(z1, xi)	...	j(zk, xi)

 

Для F-автомата Мура обе таблицы можно совместить и получить таблицу переходов, в которой над каждым состоянием z_k стоит соответствующий этому состоянию выходной сигнал y(z₀).

Автомат Мили

Xi	zk
	z0	z1	...	zk
переходы
x1	j(z0, x1)	j(z1, x1)	...	j(zk, x1)
x2	j(z0, x2)	j(z1, x2)	...	j(zk, x2)
...	...	...	...	...
xi	j(z0, xi)	j(z1, xi)	...	j(zk, xi)
выходы
x1	y(z0, x1)	y(z1, x1)	...	y(zk, x1)
x2	y(z0, x2)	y(z1, x2)	...	y(zk, x2)
...	...	...	...	...
xi	y(z0, xi)	y(z1, xi)	...	y(zk, xi)

Графовый способ задания автоматов (на основе направленных графов)

 

Граф задается следующим образом: вершины графа представляют внутренние состояния z, ребра – переходы из одного состояния в другое z_i -> z_j при воздействии входного сигнала, x_k – дуга на графе. Для задания функции выходов дуги графа отмечают соответствующим выходным сигналом.

1. Для автомата Мили – дуга маркируется входным сигналом x_k, которое вызвало переход из состояния z_i в состояние z_j. Сюда же ставится значение выходного сигнала y=y(z_j, x_k).

2. Для автомата Мура – дуга x_k дополняется выходным сигналом y=y(z_j, x_k) при z_i -> z_j.

Матричный способ задания автоматов

Матричный способ является наиболее общим способом описания автомата. Матрица соединения автомата – квадратная матрица С_ij=||c_ij||, строки которой соответствуют исходным состояниям системы, а столбцы - состояниям переходов. Элемент матрицы c_ij=x_k/y_s, где x_k – входной сигнал, вызывающий переход z_i -> z_j, y_s – значение выходного сигнала, выдаваемое на этом переходе. Для автомата Мура элемент c_ij равен множеству входных сигналов при переходе z_i -> z_j, а выход описывается вектором, i-я компонента которого – это выходной сигнал. C=||C_ij||, строки – исходные состояния, столбцы – состояния перехода.

Элемент C_ij=x_k/y_s, стоящий на пересечении i-й строки и j-го столбца (автомат Мили) – входной сигнал x_k, вызывающий переход из состояния z_i®z_j и выходной сигнал y_s.

Для автомата Мили матрица соединений:

 

(5.4)

 

Если z_i®z_j происходит под действием нескольких воздействий, то элемент матрицы C_ij – множество пар " вход – выход" для этого перехода, соединенных знаком дизъюнкции.

Для F–аппарата Мура C_ij – множество входных воздействий при переходе (z_i, z_j), а выход описывается вектором выходов

 

, (5.5)

 

где i-я компонента – выходной сигнал, отмечающий состояние z_i.

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

Рассмотрим таблицу переходов и граф асинхронного конечного автомата. Для F-автомата состояние z_R – устойчивое, если для любого входа x_iÎ X, для которого j(z_R, x_i)=z_R, имеет место Y(z_R, x_i)=y_R. Таким образом, F-автомат называется асинхронным, если каждое его состояние z_RÎ Z устойчиво.

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

1. Автомат Мили:

– табличный способ задания:

 

xi	zk
	z0	z1	z2
Переходы
x1	z2	z0	z0
x2	z0	z2	z1
выходы
x1	y1	y1	y2
x2	y1	y2	y1

 

– графовый способ задания:

 

z2

z0

z1

x1

x2

x2

x1

x2

x1

y2

y1

y1

y1

y1

 

 

 

– матричный способ задания:

		z0	z1	z2
	z0	x2/y1	–	x1/y1
C1 =	z1	x1/y1	–	x2/y2
	z2	x1/y2	x2/y1

2. Автомат Мура:

– табличный способ задания:

 

	y
xi	y1	y1	y3	y2	y3
	z0	z1	z2	z3	z4
x1	z1	z4	z4	z2	z2
x2	z3	z1	z1	z0	z0

 

– матричный способ задания:

 

		z0	z1	z2	z3	z4
	z0	–	x1	–	x2	–			y0
	z1	–	x2	–	–	x1			y1
C=	z2	–	x2	–	–	x1		Y =	y2
	z3	x2	–	x1	–	–			y3
	z4	x2	–	x1	–	–			y4

 

– графовый способ задания:

 

 

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться:

Популярное:

1. F. МОДЕЛИ ОБУСЛАВЛИВАНИЯ АДДИКЦИИ
2. IDEF1X - методология моделирования данных, основанная на семантике, т.е. на трактовке данных в контексте их взаимосвязи с другими данными.
3. OLAP-технология и многомерные модели данных
4. VI Моделирование рынка и составление прогноза выпуска автомобилей
5. АВТОРСКИЕ МОДЕЛИ ПСИХОЛОГИЧЕСКОЙ СЛУЖБЫ
6. АВТОРСКИЕ МОДЕЛИ ПСИХОЛОГИЧЕСКОЙ СЛУЖБЫ, ИЛИ КАК ОБРЕСТИ СВОЕ ЛИЦО
7. Алгоритм построения математической модели.
8. Анализ объекта моделирования
9. Анализ результатов моделирования
10. Базовые модели оценки эффективности управления организацией
11. Базовые модели политической коммуникации
12. Введение. Понятие, роль и этапы математического моделирования в экономике и финансах