11. Конечно-автоматные модели дискретных систем. Вводные понятия. Функционирование конечного автомата. Примеры.

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

Элементы, характеризующие конечный автомат как математическую схему.

1. Конечное множество водных сигналов (управлений)

Х – входной алфавит системы, т.е. х(iT) в момент времени iT принадлежит этому множеству.

2. Конечный внутренний алфавит

Т.к. для некоторых компонентов вектора Z:

z^k є Z^k, то z(iT) є Z; Z=Xⁿ_k=1Z^k

3. Конечный выходной алфавит Y

y(iT) є Y

4. Начальное состояние конечного автомата в левой границе интервала моделирования

Z₀=z(t₀)

5. Функция переходов определяет состояние конечного автомата z в момент времени iT, если в предшествующий момент времени автомат находится в состоянии z((i-1)T) и на вход системы поступило некоторое управление X(iT)

z(iT)=f(z((i-1)T),x((i-1)T)

z(i)=f(z(i-1),x(i-1))

Т.о. функция переходов f(.) может быть проинтерпритирована как функция f преобразования аргументов в дискретные модели (*), (**)

z_m+1=f(z_m, x_m, m) (*)

z_m+1¹=f₁(z_m¹, z_m²,…, z_mⁿ, x_m, m)

z_m+1²=f₂(z_m¹, z_m²,…, z_mⁿ, x_m, m)

………………………………. (**)

z_m+1ⁿ=f_n(z_m¹, z_m²,…, z_mⁿ, x_m, m)

y_m+1=q(z_m¹, z_m²,…, z_mⁿ, x_m, m)

6. Функция выходов определяется типом конечного автомата.

Различают:

- автомат Мили:

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

y(iT)=q(z((i-1)T), x(iT))

y(iT)=q(z((i-1)T), x((i-1)T))

Т.е. функция выходов q конечного автомата соответствует функции q модели дискретной системы.

- автомат Мура:

выход определяется только текущим состоянием конечного автомата

y(iT)=q(z((i-1)T))

Функционирование конечного автомата (КА)

1)КА в каждый момент времени t равный iT, находится в определенном состоянии (в начальный момент t=0 – в начальном состоянии)

2)В состоянии z((i-1)T) автомат воспринимает подаваемый на вход сигнал x(iT) и переходит в новое состояние z(iT), при этом формируется соответствующий выход y(iT).

3)В КА функция переходов и выходов задается в виде соответствующих таблиц (переходов и выходов).

Пример моделирования системы с использованием КА

Система имеет две фазовые координаты z¹, z², один вход x и один выход y. Модель дискретной системы имеет вид:

z¹(m+1)=f₁(z¹(m), z²(m),…, zⁿ(m), x(m), m)

z²(m+1)=f₂(z¹(m), z²(m),…, zⁿ(m), x(m), m)

y(m+1)=q(z¹(m), z²(m),…, zⁿ(m), x(m), m)

Множества значений фазовых координат ограничены

z¹ є Z¹={1,2,3}

z² є Z²={1,2,3}

Z=Xⁿ_k=1Z^k

Множество Z имеет вид: ????

Множество возможных значений входа ограничено и имеет вид:

x(m) є X={a,b,c}

y(m) є Y={α,β}

Т.о. для конечного автомата определены требуемые конечные множества состояний входов-выходов, поэтому функция переходов f(.) и функция выходов q(.) может быть представлена в виде соответствующих таблиц:

f(z(m),x(m),m)				q(z(m),x(m),m)
	a	b	c		a	b	c
(1,1)	(2,1)	(2,2)	(3,2)	(1,1)	β	β	α
(1,2)	(1,2)	(1,2)	(1,2)	(1,2)	β	α	α
(2,1)	(2,2)	(3,1)	(2,2)	(2,1)	α	α	β
(2,2)	(1,1)	(1,1)	(1,1)	(2,2)	β	β	β
(3,1)	(3,1)	(3,1)	(1,1)	(3,1)	α	α	β
(3,2)	(3,2)	(3,2)	(3,2)	(3,2)	α	β	β

Т.о., например, f((2,1),b)=(3,1); q((2,1),b)=α

Представление функционирования КА в виде графа состояний

1)Каждому состоянию z(i) ставится в соответствие вершина P_i графа состояний.

Вершины P_i и P_k связываются направленной дугой, при условии, что система переходит из состояния z_i в состояние z_k под действием управления X_s

2)Управления X_s, переводящие систему из состояния z_i в состояние z_k, обозначаются над соответствующей дугой. При этом выход системы, получаемый в состоянии z_k и определяемый функцией выходов, так же отмечается над соответствующей дугой.

y_k=q(z_i,X_s)

3) Из исходного состояния z_i в следующее состояние z_k система может быть переведена действием не одного управления, а нескольких, т.е. x_s, x_u, x_v. В результате в состоянии z_k может быть получено не одно значение выхода

y_s=q(z_i,x_s); y_u=q(z_i,x_u)

Тогда соответствующие значения выходов обозначаются над дугой вместе с совокупностью значений входов

12.Дискретно-вероятностные модели. Вводные понятия. Задание условных вероятностей переходов и получения выходов. Требования к условным вероятностям. Обобщенная форма совместного распределения вероятностей. Примеры.

Детерминированный автомат предполагает, что каждой паре (z_i, x_p) однозначо соответствует паре (z_l,y_s).

В вероятностном автомате каждой паре (z_i, x_p) однозначно не ставится в соответствие пара (z_l,y_s). Задаются условия реализации пары (z_i, x_p)

P(z_l,y_s/z_i,x_p)

Т.о. вероятность P(./.) – это вероятность перехода автомата в состояние z_l и получение выхода y(s) при условии, что автомат находится в состоянии z_i и на вход поступил сигнал x_p.

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

P₀(z_i)=P₀ⁱ

z	z1 z2…zl…zL
P(0)	P01 P02…P0l…P0L

Условия для начальных вероятностей: 0≤P₀ⁱ≤1, ∑P₀ⁱ=1

Функционирование вероятностного конечного автомата

Для каждой пары состояний «вход» (z_i,x_p) задается распределение вероятностей перехода системы в новое состояние и получение в этом состоянии соответствующего выхода: P(z_l,y_s /z_i,x_p)

Вывод: т.о. число распределений вероятностей переходов в новые состояния z_l и формирование выходов y_s будет равно числу возможных пар состояний «вход».

Условия для вероятностей переходов

1)0≤P_l,s^<i,p>≤1

2) , т.е. сумма вероятностей переходов в последующие состояния и получение различных выходов равна единице (при условии, что система находится в текущем состоянии z_i и на нее воздействует одно управление x_p.

Пример вероятностного автомата

Z={0,1,2,3,4}

Y={0,1}

Входной сигнал фиксирован X_p

Т.е. на систему, находящуюся в соответствующем состоянии ( в любом из перечисленных с учетом вероятностей), действует управление X_p. В результате система переходит в новое состояние и формируются новые выходы (в рассматриваемом примере предполагается, что случайным является лишь переход в новые состояния, полученные выходы являются не случайными, а детерминированными)

Вывод: для каждого возможного управления X_p формируется граф переходов. При этом описание вероятностного автомата предполагает задание законов распределений для всех пар (z_i,x_p)

Обобщенная форма вероятностного автомата

Предполагает задание для каждог иодноо состояния z_i и каждого управления X_p совместных законов распределения вероятностей переходов в соответствующие состояния и получение соответствующих выходов (т.е. случайными являются как новые состояния, так и соответствующие выходы в этих состояниях).

Пример таблицы совместного распределения вероятностей переходов в новые состояния и получения в этих состояниях соответствующих выходов

Таблица формируется для каждого состояния вероятностного автомата и каждого управления, реализуемого в этом состоянии.

Текущее состояние z_i

Управление в этом состоянии X_p

z_l – новое состояние, в которое возможен переход

y_s – соответствующие значения выхода

P_l – вероятность получения соответствующего нового состояния

P_s – вероятность получения нового выхода

Таблица

Вывод: т.о. таблица описывает вероятности для одного исходного состояния и одного управления, реализуемого в этом состоянии

13).Y-детерминированный вероятностный автомат. Свойства случайного процесса, моделируемого Y-детерминированным вероятностным автоматом. Задание вероятностей переходов. Пример моделирования системы.

Понятие Y-детерминированого вероятностного автомата

Если вх. сигнал вероятностного автомата определяется детерминорованно, то такой автомат наз. У-детерминированный.

При этом задается закон распределения вероятностей переходе из даного состояния в другое, т.е. закон распределения дне состояний z-достигаемых из исходного состояния z_i

P_e^<i> реализация любого управления может привести к этим переходам

Таким образом задается 1 закон распределения переходов из каждого исходного состояния в последующие состояния

Св-ва У-детерминированног вероятностного автомата

1 .В любой момент времени (t) состояние процесса z(t) может принять значение из бесконечного множества z= z_i

2.Вероятность переходав состояние z_e, т.е. последующее состояние, зависит только от z_i и не зависит от предшествующих состояний.

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

Пример. Функционирования конвеерной системы с учетом отказов и восстановление оборудования при использовании КМЦ.

Выполняемые работы реализуются в системе конвеерного типа выполняются 2 работы с различными маршрутами обслуживания.

Схема реализации работы

1-ая работа

2-ая работа

Каждый из приборов может находится в одном из слудеющих сосотояний:-работоспособное;-отказ прибора;-ремонт прибора;-простой прибора

Соответственого система может находится в одном из состояний:-рабочее;-отказал i-ый прибор остальные приборы (i≠S) находятся в работоспособном состоянии; - ремонт i-ого прибора, остальные приборы простаивают в ожидании окончания ремонта; -переналадка j-ых работоспособных приборов на реализацию другого выда работ.

Обозначения для состояний

- работоспособное состояние всей системы при выполнении р-ого вида работ

- состояние отказа i-ого прибора при работоспособном состоянии других j-ых приборов

- состояние ремонта i-ого прибора, все остальные приборы в ожидании окончания ремонта

- состояние переналадки системы на выполнение альтернативного, p-ого вида работ

- заданные вероятности отказа приборов

- заданные вероятности системы

Имеются 2 стратегии восстановления системы:1.)стратегия ремонта; 2)стратегия переналадки на выполнение другого вида работ.