Способы задания автоматов

Размещено на http://www.allbest.ru/

Способы задания автоматов



1. Некоторые понятия в теории абстрактных автоматов

В литературе по классическим автоматам [12-14; 18-19; 21; 24; 26; 32; 90; 125; 140] даны некоторые важные понятия о взаимоотношениях между автоматами, такие, как: эквивалентность между автоматами, изоморфизм абстрактных автоматов, взаимоотношения между автоматами первого (Мили) и второго (Мура) рода.

Рассмотрим эти понятия.

Определение 1. Два абстрактных автомата с общим входным и выходным алфавитом называются эквивалентными между собой, если они индуцируют одно и то же отображение множества слов во входном алфавите в множество слов в выходном алфавите.

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

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

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

2.Табличные и графические способы задания классических автоматов Мили и Мура

Задание классического монофункционального абстрактного автомата А сводится к заданию функций переходов д и функций выходов л. Из соображений практики остановимся более подробно на способах задания автоматов с помощью таблиц и графов. Обычно для автоматов Мили функции переходов и выходов (2.3) задаются соответствующими таблицами с двумя входами. Столбик таблицы переходов 1 и таблицы выходов 2 обозначает состояние автомата а_i (а_i Q), а строка - входной сигнал х_k (х_k Х).

Таблица 1

Таблица 2

На пересечении столбиков и строк таблицы переходов 1 ставится новое состояние автомата а_s(t), в которое автомат переходит под воздействием входного сигнала х_k(t) из предыдущего состояния а_i(t - 1), то есть а_s(t) = =д(а_i(t-1), х_k(t)).

На пересечении столбиков и строк таблицы выходов 2 ставится выходной сигнал автомата у_s(t), который автомат выдает под воздействием входного сигнала х_k(t) и предыдущего состояния а_i(t - 1), то есть у_s(t) = л(а_i(t - 1), х_k(t)).

Для автоматов Мура функции переходов и выходов (2.4) задаются соответствующей одной отмеченной таблицей Столбик таблицы переходов в отмеченной таблице 3 задается аналогично, как это делается в таблице переходов 1 автомата Мили. Это связано с тем, что функции переходов в автоматах Мили и Мура совпадают (см. формулы (2.3) и (2.4)). Однако, функции выходов в автоматах Мура у_i(t) = л(а_i(t)), зависят только от одной переменной состояния а_i (а_i Q). В связи с этим в таблице переходов добавляется строка над строкой наименования состояний а_i, в которой отмечаются выходные сигналы у_i, которые зависят от соответствующих а_i состояний автомата.

Таблица 3

Таким образом, с помощью таблиц 1 - 3 можно полностью задать функционирование автомата Мили или Мура в автоматном дискретном времени t. В автоматном непрерывном времени у²(Т) выходной сигнал автомата Мура описывается более подробно и более точно в (2.16).

Более наглядно задается функционирование автомата Мили с помощью направленных графов, у которых состояния а_i автомата отображается в кружочках (вершинах графа), а переходы из одного состояния а_iв другое а_k отображается стрелочкой, над которой устанавливается символ х_k входного сигнала, способного перевести автомат в состояние а_k. Выходные сигналы у_i автомата Мили отображаются рядом с х_k входными сигналами, в связи с тем, что они зависят от тех же переменных и появляются в одно и тоже автоматное время t.

Функционирование автомата Мура с помощью направленных графов, у которых состояния а_i автомата отображается в кружочках (вершинах графа), а переходы из одного состояния а_iв другое а_k отображается стрелочкой, над которой устанавливается символ х_k входного сигнала, способного перевести автомат в состояние а_k. Выходные сигналы у_k автомата Мура отображаются рядом с состояниями а_k, в которые перешел автомат. Это связано с тем, что у_k выходной сигнал появляется на выходном узле после перехода автомата в новое а_k состояние, о чем говорит сдвинутая функция выходов автомата Мура.

Рис. 1. Направленный граф автомата Мили



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

Задание многофункциональных абстрактных автоматов 1-го, 2-го и 3-го рода сводится к заданию соответствующих однозначной функций переходов д_o,функций выходов л₁, л₂, л₃, функцией сохранения состояний д_e и функции укрупненных переходов д_y. Остановимся более подробно на способах задания автоматов с помощью таблиц и графов.

Описание работы многофункционального автомата первого рода задается множествами (не менее двух) таблиц переходов, множествами таблиц выходов и таблицей сохранения состояний. Проиллюстрируем задание многофункционального автомата А₁первого рода в таблицах 4 - 8.

Строки в таблицах 4 - 8 соответствуют входным сигналам х_i, а столбцы - блокам р₁ состояний, сохраняющих е_j входных сигналов. Обычно крайний столбец в таблицах обозначен начальным состоянием а₀.

На пересечении строк и столбцов таблиц однозначных переходов ставится состояние а(t)= (а(?-1), х(t)), в котором автомат 1-го рода переходить из состояния а(?-1) под воздействием информационного х(t) входного сигнала в состояние а(t) в тактовый момент t автоматного непрерывного времени Т. В таблицах выходов автомата 1-го рода - соответствующий переходу выходной сигнал у(t)= л₁(а(?-1), х(t)) типа 1.



Таблица 4

Таблица 5

Таблица 6



Таблица 7

Строки таблицы сохранения состояний (табл. 8) соответствуют сохраняющим е(?) входным сигналам, а столбцы - а(?) состояниям автомата. В каждой строке на пересечении со столбцами в таблице сохранения состояний ставится соответствующее состояние а(?)=д_е(а(t), е(?)), где а р_j, а(t) = =а(?) (р_j Q), сохраняемое под воздействием сохраняющего е(?) входного сигнала во время внутреннего такта ? автоматного непрерывного времениТ, а в остальных случаях ставятся прочерки.

Таблица 8

При описании работы многофункционального автомата А 2-го рода выходной сигнал зависит только от запоминаемых состояний блока р_j автомата, которые устанавливаются в тактовый момент t и сохраняются во время реализации функций сохранения состояний во время внутреннего такта ? автоматного непрерывного времени Т.

Автоматы 1-го и 2-го рода способны осуществлять функции переходов в тактовый момент t автоматного непрерывного времени Т под воздействием информационных х(t) входных сигналов.

Работа автомата 2-го рода может быть задана с помощью отмеченных таблиц функций д_oоднозначных переходов вместе с функцией л₂ таблицы выходов типа 2 и таблицы сохранения состояний (табл. 8). Пример табличного описания автомата 2-го рода А₃ приведен в таблицах 8 -10.

Автоматы 3-го рода качественно отличаются от автоматов 1-го и 2-го рода тем, что они способны осуществлять переходы из одного состояния в другое не только в тактовый момент t под воздействием информационных х(t) входных сигналов, но и во время внутреннего такта ? под воздействием сохраняющих е(?) входных сигналов автоматного непрерывного времени Т. Это принципиальное отличие автоматов 3-го рода позволяет им осуществлять переходы в матричной структуре схем автоматной памяти (МФСП), которые происходят не только в блоках р_j состояний в тактовый момент t, представляющих строку состояний МФСП , но и в блоках м_i во время внутреннего такта ?, представляющих столбец состояний МФСП, за один внешний тактТ автоматного непрерывного времени.

Таблица 9



Таблица 10

Автоматы 1-го, 2-го и 3-го рода также отличаются своими функциями л₁, л₂ и л₃ выходных сигналов, рассматриваемых в автоматном непрерывном времени Т.

Функция выходов л₁ автоматов 1-го рода реализуется только в тактовый момент t под воздействием информационных х(t) входных сигналов и состояний автомата а(?-1), то есть у(t)= л₁(а(?-1), х(t)), где у Y_I.

Функция выходов л₂ автоматов 2-го рода реализуется в тактовый момент t после перехода автомата в новое состояний под воздействием информационных х(t) входных сигналов и предыдущего во времени состояния автомата а(?-1). Функция выходов л₂, во первых, является по этому сдвинутой по сравнения с началом тактового момента t, а также зависит только от вновь установленного состояния а(t) и сохраняемого состояния а(?), где а(t) = а(?) и у(Т) = л₂(а(t), а(?)), где у Y_II.

Функция выходов л₃ автоматов 3-го рода реализуется во время внутреннего тактового момент ? в новое состояний под воздействием сохраняющих е(?) входных сигналов и состояний автомата а(?). Функция выходов л₃,во первых, является сдвинутой по сравнения с началом внутреннего тактового момента ?, а также зависит только от вновь установленного состояния а(?) и от сохраняющего е(?) входного сигнала, то есть у(?)= л₃(а(?), е(?)), где у Y_III.

Работа автомата 3-го рода может быть задана с помощью таблиц функций д_oоднозначных и отмеченных таблиц функцийд_y укрупненных переходов вместе с функцией л₃ таблицы выходов типа Пример табличного описания автомата 3-го рода А₃ приведен в таблицах 11-14 и таблицы сохранения состояний (табл. 8).

Таблица 11

Таблица 12



4. Табличные способы задания абстрактных вероятностных автоматов 3-го рода

В отличие от детерминированных автоматов, в которых возможен только однозначный переход от одного состояния в другое под воздействием элементарных однозначных р₀(T) и укрупненных р_у(T) входных слов, в вероятностных автоматах осуществляется переход в состояние определенного блока р_j состояний автомата с определенной вероятностью Р_е перехода под воздействием элементарных вероятностных р_в(T) входных слов.

Вероятностный абстрактный автомат 3-го рода первого типа задается с помощью таблицы сохранения состояний, как и в детерминированных автоматах (табл. 8), таблицы однозначного перехода в а_р(t) состояние (табл. 15-16), отмеченной таблицы переходов в а(Д) состояние блока р_j состояний (табл. 17) с определенной вероятностью Р_е перехода.

Таблица 13



Таблица 14

Таблица 15

Вероятностный абстрактный автомат 3-го рода второго типа задается с помощью таблицы сохранения состояний, как и в детерминированных автоматах (табл. 8), таблицы однозначного перехода в а(t) состояние (табл. 18-19), отмеченной таблицы переходов в а(Д) состояние блока р_j состояний (табл. 20) с определенной вероятностью Р_е перехода.



Таблица 16

Таблица 17

Таблица 18



Таблица 19

Вероятностные переходы в автомате 3-го рода первого типа происходят в определенном блоке р_j состояний, а в автомате 3-го рода второго типа происходят в определенном блоке µ_і состояний. Таким образом, вероятностные автоматы 3-го рода первого типа и вероятностные автоматы 3-го рода второго типа осуществляют вероятностные переходы в состояния вполне определенных подмножеств соответствующих блоков р_j и µ_і состояний с определенной мерой вероятности.

Автоматы 4-го рода задаются таблицами переходов (15) - (16), а выходной сигнал у⁴(t) = л₄(x_p(t), a_p(t)) зависит от входного сигнала x_p(t) и установленного однозначного состояния базовой схемы памяти a_p(t), которое не сохраняется ни при каких сохраняющих e(Д) входных сигналов. После окончания этого сигнала детерминированные автоматы должны устанавливаться в начальное состояние а₀.



5. Табличный способ задания абстрактных нечетких автоматов 3-го рода

Абстрактный нечеткий автомат 3-го рода задается с помощью таблиц сохранения состояний, как в многофункциональных детерминированных автоматах (табл. 8), таблицы однозначного перехода в а_р(t) состояние, как в вероятностных автоматах 3-го рода первого типа (табл. 15-16), и отмеченной таблицы переходов в а(Д) состояние блока р_j состояний (табл. 21) с определенной вероятностью Р_н перехода.

Таблица 20

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

Абстрактные автоматы с памятью используются для реализации функций однозначного перехода в новое состояние а_і(t) при соответствующем входном сигнале х(t) при условии сохранения этого состояния после окончания сигнала х(t), то есть во времени внутреннего такта Д автоматного непрерывного времени Т.

Однозначные переходы в абстрактных детерминированных автоматах 1-го и 2-го роду изображает рис.

Рис.3

Выходные сигналы абстрактных автоматов 1-го и 2-го рода соответственно изображаются в графе либо на дуге перехода из одного состояния в другое в автоматах 1-го рода, либо возле вершины графа в автоматах 2-го рода.

Многофункциональные детерминированные абстрактные автоматы 3-го рода используются не только для реализации функций однозначного перехода в новое состояние а(t) при соответствующем устанавливающем х(t) входном сигнале при условии сохранения этого состояния после окончания сигнала х(t), но и при использовании переходов во время внутреннего такта Д для реализации укрупненного перехода в новое состояние а (Д) при соответствующем е(Д) входном сигнале, как это изображено на рис. 4.

Рис.4

Выходные сигналы абстрактных автоматов 3-го рода соответственно изображаются, как и в автоматах 2-го рода, возле вершины графа.



Рис.5

Вероятностные абстрактные автоматы первого и второго типа 3-го рода используются для реализации функций вероятностного перехода в новое состояние а(Д) при соответствующих входных элементарных словах р_в1(T)) или р_в2(T) с определенной вероятностью Р_е во время внутреннего такта Д, как это изображено на рис. 5 (для вероятностного автомата 3-го рода первого типа и автомата 4-го рода) и на рис. 6 (для вероятностного автомата 3-го рода второго типа).

Рис.6

Нечеткие абстрактные автоматы 3-го рода используются для реализации функций нечеткого перехода в новое состояние а(Д) при соответствующем входном элементарном слове р_н(T) с определенной вероятностью Р_н во время внутреннего такта Д, как это изображено на рис. 7.



Рис.7

Таким образом, многофункциональные абстрактные автоматы увеличивают типы переходов, используемых в классических абстрактных автоматах Мили и Мура, расширяют понятие функционирования автомата с дискретного автоматного времени t до непрерывного автоматного времени T, что дает возможность более глубоко исследовать их работу.



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

Рис.8

графический автомат абстрактный

Последовательные многофункциональные автоматы Мараховского 1-го, 2-го и 3-го рода, имеющие два множества входных алфавитов: Х - информационный входной алфавит иЕ - сохраняющий входной алфавит, способен настраиваться другим многофункциональным автоматом через множество букв е_j (е_j Е) сохраняющего входного алфавита на функционирование в определенном блоке (подмножестве) своих состояний. В этом случае образуется многоуровневая (иерархическая) структура абстрактногоF_и-автомата из последовательных многофункциональных подавтоматов S_i (i=1, 2, …, n). Организация такой объединенной структуры иерархического автомата (ИА) представлена на рис. 8.

Каждый многофункциональный подавтомат S_i (i=1, 2, …, n) иерархического абстрактного F_и-автомата может переходить из одного состояния в другое параллельно с другими подавтоматами ИА (рис. 8). Функционирование подавтомата S_i в определенном подмножестве состояний может быть изменено воздействиями входных букв информационного алфавита Х в тактовый момент t и воздействиями результатов работы других подавтоматов S_iИА буквами сохраняющего входного алфавитаЕ в моменты внутреннего такта ? автоматного непрерывного времени Т.

Дадим определение абстрактного иерархического F_и-автомата.

Определение 2. Математической моделью иерархического дискретного устройства с многофункциональной системой организации памяти является абстрактный иерархический F_и-автомат, определяемый как N-компонентный вектор

компоненты S_i которого задаются шестнадцатикомпонентным вектором

у которого

Ш X_i- множество информационных входных сигналов;

Ш E_i - множество сохраняющих входных сигналов;

Ш Z_i - множество разрешающих входных сигналов;

Ш - множество выходных сигналов типа 1;

Ш - множество выходных сигналов типа 2;

Ш - множество выходных сигналов типа 3;

Ш Q_i - произвольное множество состояний;

Ш - множество блоков состояний подавтомата S_i;

Ш - начальный сохраняющий входной сигнал;

Ш - начальное состояние подавтомата S_i;

Ш : Q_iX_i>Q_i - однозначная функция переходов;

Ш : Q_i>- функция сохранения блоков состояний;

Ш : Q_iE_i >- функция укрупненного перехода;

Ш : Q_iX_i> - функция выходов типа 1;

Ш : > - функция выходов типа 2;

Ш : Q_iE_i >- функция выходов типа 3

и определенный функционально, как и компоненты структуры S_i, шестнадцатикомпонентным вектором

у которого

Ш X={X₁, X₂, …, X_N}- множество информационных входных сигналов;

Ш E ={E₁, E₂, …, E_N}- множество сохраняющих входных сигналов;

Ш Z_i ={Z₁, Z₂, …, Z_N}- множество разрешающих входных сигналов;

Ш ={}- множество выходных сигналов типа 1;

Ш ={}- множество выходных сигналов типа 2;

Ш ={}- множество выходных сигналов типа 3;

Ш Q ={Q₁, Q₂, …, Q_N}- произвольное множество состояний;

Ш ={,,…, }- множество блоков состояний подавтомата S_i;

Ш E₀= - начальный сохраняющий входной сигнал;

Ш a₀ = - начальное состояние подавтомата S_i;

Ш F₁: QX> Q - однозначная функция переходов, реализующая отображение D_F1 QX в Q;

Ш F₂: Qе_j> р_j - функция сохранения блоков состояний, реализующая отображение D_F2 Qе_j в р_j;

Ш F₃: QE> р_j - функция укрупненного перехода, реализующая отображение D_F3 QE в р_j;

Ш л₁: QX> - функция выходов типа 1, реализующая отображение D_л1 QX на ;

Ш л₂: р_j >- функция выходов типа 2, реализующая отображение D_л2 р_jна;

Ш л₃: QE >- функция выходов типа 3, реализующая отображение D_л3 QЕ на .

Подавтоматы S_i, реализующие свою автоматную память на регистрах открытого типа, функционируют в автоматном непрерывном времени Т.

В начальный тактовый момент t₀ все под автоматы S_i устанавливаются в начальное состояние а₀ соответствующим входным сигналом Во время последующего внутреннего такта ?₀ начальное состояние а₀ сохраняется под воздействием начальных сохраняющих (?₀) входных сигналов. Объединение состояний подавтоматов S_i определяют состояния а_i иерархичного автомата в данный тактовый момент t_i или ?_i автоматного непрерывного времени Т_i. В иерархичном автомате А во время тактового момента t_iвсе или только некоторые подавтоматы S_i могут осуществлять функции однозначных переходов, реализуя общую функцию однозначных переходов F₁ иерархического автомата А в новое состояние Во время внутреннего такта ?_i подавтоматы S_i могут осуществлять укрупненные переходы , реализуя общую функцию перехода F₃ иерархического автомата А в новое состояние Если подавтоматы S_i за время всего внешнего тактаТ не совершают переходы в новое состояние, то, следовательно, они реализуют функцию сохранения состояний , реализуя в ИА А объединенную функцию сохранения состояний F₂.

Каждый из подавтоматов S_i работает в определенном блоке состояний всего множества своих состояний Q_i. Блоки состояний подавтоматов S_i образуют в ИА А определенный блок множества блоков состояний, в котором ИА А функционирует в данный момент времени.

Характерной особенностью ИА А является возможность взаимодействия подавтоматов S_i не только во время такта t_i, но и во время внутреннего такта ?_i автоматного непрерывного времени Т_i. Память подавтоматов S_i представляет собою матричную структуру, в которой во время такта t_i под воздействием информационных х_і(t) входных сигналов подавтомат S_i способен перейти из одного состояния в другое в одном блоке состояний (строке матричной структуры схемы автоматной памяти). А во время внутреннего такта ?_i под воздействием сохраняющих е_j(?) входных сигналов подавтомат S_i способен перейти из одного состояния в другое в одном блоке µ_i (столбике матричной структуры схемы автоматной памяти), то есть из определенного состояния одного блока в определенное состояние другого блока состояний.

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



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

Автомат удобно описывать алгоритмически, рассматривая его функционирование последовательно при каждом переходе из одного состояния в другое за время одного внешнего такта Т_i автоматного непрерывного времени. Наглядным способом задания классических автоматов с памятью на триггерах является задание их в виде микропрограммы [125] или в более обобщенном виде автограммы [26].

Для алгоритмического описания иерархических автоматов с автоматной памятью с общим состоянием, состоящим из частичных состояний подавтоматов S_i, предложен термин «полиграмма» по следующим соображениям. Во-первых, термин «микропрограмма», «автограмма» и другие способы задания автоматов с памятью на триггерах ориентированы вполне обоснованно на описания функций переходов в автоматах только во время тактового момента t_i, имеют сильное ограничение, не позволяющее описывать работу автомата во время внутреннего такта ?_i автоматного непрерывного времени Т_i. Во-вторых, понятия «микропрограмма», «автограмма» и другие способы задания классических автоматов ориентированы на реализацию запоминаемого состояния в регистре на триггерах.

В связи с этим, термины «микропрограмма», «автограмма» не подходят при описании общего состояния регистров на схемах автоматной памяти. Термин же «полиграмма» ассоциируется со схемной реализацией управления на многоуровневых регистрах с многофункциональной системой организации памяти, которую называют многоуровневой иерархической автоматной реализацией [64]. В-третьих, полиграмма ориентирована не только на преобразование входной информации в выходную информацию, но и на изменение области запоминаемых состояний автомата, которая определяется сохраняющим е_j(?) входным сигналом. Эта особенность позволяет использовать полиграмму при описании иерархической структуры автомата, способной преобразовывать входную информацию и изменять внутреннюю структуру преобразования информации [64].

Полиграмма описывает каждое состояние иерархического автомата (ИА) А как объединение состояний подавтоматов S_i.

В каждом пункте полиграммы описываются режимы работы подавтоматов S_i за один внешний такт Т автоматного непрерывного времени. За один внешний такт ТИ А А воспринимает входное слово R_k(T), состоящее из совокупности элементарных р_i(T) входных слов подавтоматов S_i

Под воздействием входного слова R_k ИА А способен перейти в новое состояние a_sи выдать выходные сигналы (і=1, 2, 3), состоящие из совокупности выходных сигналов определенных типов подавтоматов S_i

,

где выходные сигналы , , определяются соответственно по функциям выхода, описываемые в уравнениях (2.15)-(2.17).

При неизменяемых сохраняющих е_і(?) входных сигналах подавтоматы S_i функционируют в определенных блоках своих состояний, а, следовательно, и ИА А функционирует в те же периоды времени в определенных блоках р_k своих состояний

Каждое состояние а _і подавтомата S_i сохраняет свое значение при соответствующих сохраняющих е_j входных сигналах. Изменение сохраняющего е_j входного сигнала в подавтомате S_i происходит в тактовый момент t в зависимости от выходных сигналов , поступающих от других подавтоматов S_i в соответствии с алгоритмом решения задачи, и во время внутреннего такта ? сохраняющий е_і(?) входной сигнал определяет область запоминаемых состояний (блок состояний) подавтомата S_i. Сохраняющие е_і(?) входные сигналы однозначно определяют блоки состояний, в которых работает подавтомат S_i, а совокупность Е_k сохраняющих е_і(?) входных сигналов однозначно определяет блок р_k состояний, в которых работает ИА А

Пункт полиграммы при детерминированном элементарном входном слове R_k записывается в следующем виде:



где K - состояние ИА А;

Е- сохраняющий входной сигнал ИА А;

R_j(j=1, 2, …, m) - элементарное входное слово ИА А;

K_j(j=1, 2, …, m) - состояние ИА А, к которому совершается переход от состояния K при выполнении строки j;

Е_j(j=1, 2, …, m) - сохраняющий входной сигнал, при котором запоминается состояние K_j;

- выходной сигнал типа і ИА А.

Каждая строка (R_j - K_jE_j) пункта KE полиграммы описывается в виде S_kстрок

где q - число строк S_k(k= 1, 2, …,, m ), имеющихся в описании строки полиграммыj (j=1, 2, …, m);

- элементарное входное слово строки S_k;

- выходной вектор строки S_k;

- состояние подавтомата S_i, к которому совершается переход от состояния а_і в состояние а_k при выполнении строки S_k;

е_і - сохраняющий входной сигнал состояния а_і.

Такое описание поведения ИА А в состоянии КЕ является пунктом иерархического алгоритма функционирования автомата А.

Пункт полиграммыКЕ, как видно из описания поведения ИА А, имеет иерархическую структуру, то есть вначале описываются обобщенные состояния К₀, К₁, …, К_m, обобщенные элементарные входные слова R_j(j=1, 2, …, m), обобщенные входные сигналы Е₀, Е₁, …, Е_m, а затем каждая строка пункта полиграммы разворачивается в S_k(k= 1, 2, …,, m ) строк, которые реализуются в подавтоматах S_iИА А, осуществляя переход из одного состояния а_і в состояние а_k при выполнении строки S_k. Во время функционирования ИА А некоторые, а, возможно, и все подавтоматы S_i могут не изменять своих состояний на каком-то отрезке автоматного времени. Тогда при описании полиграммы ИА А в конце строк будут обозначения состояний, которые совпадают с начальным обозначением пункта полиграммы или пункта строки полиграммы.

Каждая j-я строка пункта полиграммы КЕ состоит из следующих элементов, функционирование которых описывается в автоматном непрерывном времени Т: обозначение самого пункта КЕ, отображающего состояние К(?-1), сохраняемое при входном сигнале Е(?-1); элементарного входного слова R_j(Т), состоящего из последовательных соответственно информационного Х _j(t) входного сигнала и сохраняющего Е_j(?) входного сигнала; выходных сигналов, описываемых уравнениями (5)-(7).

Содержательный смысл каждой j-й строки полиграммы заключается в установлении связи между состояниями К(?-1) ИА А в предыдущем внешнем такте Т_i-1 и реакцией ИА А в следующем внешнем такте Т_i- при переходе в состояние К_j(?).

Каждая j-я строка полиграммы может быть представлена из трех частей. Первая часть задает вектор R_j, вторая - вектор выходных сигналов, а третья часть определяет функцию F₂ однозначного сохранения вектора K_j состояний либо функцию F₃ укрупненного перехода в состояние K_s при векторе Е _j сохраняющего входного сигнала.

Вектор Е_j сохраняющего входного сигнала при реализации функции F₂ однозначного сохранения вектора K_j состояний задает определенный блок р_j запоминаемых состояний ИА А, в котором он функционирует в данный момент Д автоматного непрерывного времени Т, а при реализации функции F₃ осуществляет укрупненный переход в состояние K_s в момент внутреннего такта Д автоматного непрерывного времени Т. Входной сигнал Е_j обеспечивает межуровневую связь подавтоматов S_iв ИА А в момент внутреннего такта Д автоматного непрерывного времени Т.

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

Преобразование тем совершеннее, чем более сложную и лучше организованную структуру системы она сопровождает.

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

Опишем некоторые основные типы строк полиграммы.

Строку полиграммы, имеющий вид

KE. R_j - K_jE_j,

графический автомат абстрактный

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



Например, строку вида

KE. Е_i - K_jE_j при Е_i ? E_j

назовем строкой перехода третьего рода, поскольку в ней описан переход, осуществляемый под воздействием только компоненты вектора Е_i сохраняемых входных сигналов. В этом случае Х_i= Ш, а Е_iR_i.

Строку вида

KE. R_j> Ш - K_jE_j,

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

Строку вида

KE. R_j - Ш,

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

При совпадении векторов Е_iиE_j в строке их можно опустить. Строка тогда (например, общая) принимает такой вид

K. R_j - K_j,

а векторы Е_iиE_j (Е_i=E_j) в данном случае подразумеваются и задают вполне определенный блок р_j (K,K_jр_j) запоминаемых состояний. Такая строка (16) называется С-вида и используется при описании микропрограммы или автограммы [26] автоматов Мили, Мура и С-автомата, которые используют в качестве памяти триггеры в регистрах, состояния которых сохраняются при одном сохраняющем е(Д) входном сигнале. Такое описание микропрограммы лишний раз подчеркивает, что автоматы Мили, Мура и С-автомата являются подмножеством многофункциональных автоматов Мараховского, на основе которых рассматривается полиграмма, описывающая ИА А, построенный на схемах автоматной памяти.

Отметим одну важную особенность выходных векторов ИА А. Упомянутые выше компоненты векторов (5)-(8) одновременно во внешнем такте Т могут инициировать различные операции в управляемых объектах, а также функциональное отключение одного из подавтоматов S_iИА А, при определении его ненадобности или ошибочности в работе. Это свойство является важным при создании отказоустойчивых цифровых устройств [8].

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

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

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

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

графический автомат абстрактный



9. Формулирование полиграммы

Работать с полиграммой упрощается, если соблюдать следующие правила.

1. Пункт полиграммы удобно обозначать двумя номерами, отмеченными символами K и E. Например, 12K,2E.

2. Начальный пункт обычно имеет номер 1K,1E, а остальные пункты полиграммы нумеруются числами до максимального номера с символом K и до максимального номера с символом E.

3. Пункты в полиграмме целесообразно располагать в порядке возрастания в начале номера с символом K, без изменения номеров возле символа E, а после изменения номера с символом E нумерацию с символом K можно начинать с начала, то есть с номера 1K.

4. Пункты, образующие в полиграмме непрерывную последовательность при одном номере с символом E, удобно нумеровать непрерывным рядом чисел.

5. Установочные пункты не имеют конкретных номеров, так как при подсчете количества пунктов в полиграмме они не учитываются. Целесообразно место установочного пункта определять в начале нумерации чисел с символом K при определенном номере с символом E.

Примечание. Перед запуском работы полиграммы целесообразно проверить на катастрофические отказы схемы памяти подавтоматов S_i ИА А, как это делалось в автомате 4-го рода. При обнаружении катастрофических отказов такие подавтоматы S_i ИА А должны быть отключены от функционирования и заменены новыми (работоспособными) или учтены при работе полиграммы.

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

Задание автомата в табличном виде, в виде графа, в виде полиграммы или каким-то другим способом является творчеством проектировщика. Проектировщик перед заданием автомата, с одной стороны, должен полностью разобраться в работе объекта и временных последовательностях управляющих воздействий, необходимых при управлении объектом, а с другой стороны - владеть методами формального синтеза автоматов по полиграмме на доступной ему элементной базе со схемами автоматной памяти сверхбольших интегральных схем (СБИС). Проверка правильной (корректной) работы полиграммы или спроектированного управляющего устройства может быть выполнена средствами моделирования устройства на компьютере [74].

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

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

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

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

2. Процесс расщепления общей информации алгоритма на уровни возможен при иерархическом характере обработки информации во время решении задачи.

3. При описании иерархического процесса обработки информации целесообразно рассматривать, во-первых, раздельно каждый процесс в виде своей частной полиграммы, и, во-вторых, каждый пункт частной полиграммы рассматривать во временной последовательности как пункт всей полиграммы.

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

5. Временная последовательность пунктов полиграммы должна приводить управляемый объект в требуемое состояние. В этом и находит выражение иерархический (или любой другой) алгоритм решения задачи.

6. При написании полиграммы необходимо достаточно подробно описать входные и выходные сигналы управляемого объекта и представить их в кратких и выразительных обозначениях, чтобы не создавать при этом сложности при формулировании пунктов полиграммы.

7. Формулирование полиграммы надо начинать с установочного пункта. Если в полиграмме предусмотрено несколько установочных пунктов, то начинать можно с произвольного, если между ними нет приоритета.

8. Структура полиграммы должна отражать автоматный принцип многократного преобразования информации за счет возврата в исходное положение. В связи с этим в полиграмме должен быть путь из начального пункта через последовательность пунктов к начальному пункту. В связи с этим целесообразно вначале описать пункт за пунктом цикл с начальным пунктом (состоянием), а затем промежуточные циклы полиграммы.

9. Необходимо проверить согласование во времени процессов, происходящих в управляемом объекте и в автомате. При несогласовании во времени процессов необходимо скорректировать полиграмму.

После написания полиграммы и проверки ее на согласование во времени процессов, происходящих в управляемом объекте и в автомате, считается, что задание ИА А полиграммой закончено.



Заключение

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

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



Литература

1.Информационные технологии в менеджменте (управлении). Учебник и практикум. - М.: Юрайт, 2015. - 480 c.

2.Информационные технологии для финансовых менеджеров. - М.: Издательский центр БГУ, 2017. - 480 c.

3.Компьютерное моделирование менеджмента / А.Ф. Горшков и др. - М.: Экзамен, 2016. - 528 c.

4.Корнеев, И. К. Защита информации в офисе / И.К. Корнеев, Е.А. Степанов. - М.: Проспект, ТК Велби, 2016. - 336 c.

5.Кычкин, Алексей Оперативная оценка состояния сосудов человека / Алексей Кычкин. - М.: LAP LambertAcademicPublishing, 2016. - 188 c.

6.Мердок, Мэттью Взрыв обучения. Девять правил эффективного виртуального класса / МэттьюМердок ,Трейон Мюллер. - М.: Альпина Паблишер, 2016. - 192 c.

7.Одден, Ли Продающий контент. Как связать контент-маркетинг, SEO и социальные сети в единую систему / Ли Одден. - М.: Манн, Иванов и Фербер, 2017. - 446 c.

8.Петрова, Л. В. Программа Юнеско "Информация Для Всех". Отчет 2004-2005 Гг. / Л.В. Петрова, Е. И. Кузьмин ; В. Р. Фирсов. - Москва: РГГУ, 2015. - 128 c.

9.Сенкевич, Г. Е. Информационная система малого предприятия "с нуля". Самое необходимое / Г.Е. Сенкевич. - М.: БХВ-Петербург, 2016. - 400 c.

10.Слынько, Юрий Регистрация изображений и сопровождение объектов / Юрий Слынько. - М.: LAP Lambert Academic Publishing, 2015. - 116 c.

11.Современные IT-решения для финансовой индустрии (+ CD-ROM): моногр. . - Москва: Высшая школа, 2017. - 560 c.

Размещено на Allbest.ru