46727 (762378), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Автомат исполняет функции переходов для принятия решения о выборе следующего состояния. Функции переходов программируются с помощью анализа действий участников документооборота. Производимое действие определяет результирующее состояние, для которого входными данными для определения выбора являются текущее состояние документа и участник процесса. Автомат реализует документооборот, в котором на каждом шаге происходит действие на основании процесса, и на основании анализа текущего состояния документа (исполнителя) принимается решение о следующем состоянии документа. Функция перехода автоматной модели является i-м элементом множества действий {Д} документооборота, после выполнения которого происходит смена состояния на состояние .

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

Программирование автомата осуществляется путем установления соответствия между нотацией конечного автомата и композитного документооборота. То есть, после проведения декомпозиции процессов и синтеза модели {У, Д, Ф} строится автоматная модель документооборота, которая определяется пятеркой (A, S, , T, F), где {{A}≡ {У}, {S}≡ {Ф}, = ,{S}≡ { }, {F}≡ {Д}}. При этом на каждом шаге автомата, множества соответствуют множествам, описывающим жизненный цикл модели документооборота. На каждом шаге существует соответствие и : {( = ),( = ), = , = }.

3.4. Иерархический конечный автомат

Для представления иерархического конечного автомата документооборота будем использовать описание ИКА из работы [9]. В соответствии с этим описанием ИКА представляется пятеркой (I, O, S, T, r), где I и O описывают множества входных и выходных алфавитов, S представляет множество состояний, функции переходов , r задает начальное состояние. Детерминированный ИКА может быть представлен шестеркой (I, O, S, , r), где описывает выходную функцию, описывает функции переходов.

О данной паре входных и выходных последовательностей , где и говорят, что она принимается ИКА T=(I, O, S, T, r), если существует последовательность состояний такая, что для всех j=0,…,t-1 и .

В настоящей статье будем рассматривать поведение ИКА, определенного отношением элементов входа и выхода. Иными словами, отношение между алфавитами входа и выхода есть набор пар входов и выходов, которые определяют состояния детерминированного ИКА. Для заданного автомата T=(I, O, S, T, r) поведение между входом I и выходом O содержится в функциях переходов T, если каждая пара последовательности входов и выходов реализуется в T. Рассмотрим реализацию ИКА, управляющего конечными автоматами на примере на рис. 1.

MM2M1XUVZ

Рисунок 1. Пример иерархического конечного автомата.

Итак, заданные автоматы M=(I, O, S, ,r) и M2 = ( ). Предполагается, что система документооборота может принимать сразу несколько состояний, в то время как один исполнитель производит смену состояния только на одно из возможных. Таким образом, автомат M может быть НДКА, в то время, как автомат M2 может быть только ДКА. Выходная функция автомата M2 состоит из , которые соответственно определяются выходными функциями U и Z.

Заданы подмножество из множества состояний S и вход x автомата M, зададим как множества всех возможных выходов. То есть в том и только том случае, если существует такое, что . Аналогично, будет множеством всех возможных состояний, то есть в том и только том случае, если такое, что .

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

При заданном автомате детерминированный конечный автомат считается реализуемым на M1, если существует хотя бы одна пара цикличных реализаций M1 и M2, таких, что их соединение не вызывает цикла между U и V.

При заданных автоматах и ДКА является допустимым автоматом, если автомат M1 реализуем и поведение содержится в M, где является выходным результатом M. Поведение, которое реализуется допустимым автоматом, является допустимым поведением.

3.4.1. Свойства ИКА

Рассмотрим применение НДКА для реализации ИКА. Пусть при данном надо получить и для заданного , где означает мощность множества S. Пусть при этом и являются подмножествами , а и . Функция перехода существует, т.е , если выполняются три следующих условия:

1) ;

2) ;

3) .

В каждом из вычислений есть множеством подмножества . Причем пустое подмножество {0} тоже может входить во множество . При заданном множество вычисляется следующим образом: в том и только том случае, если также или .

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

Пусть будет такой связью, что в том и только в том случае, если или .

Значит, мы можем определить ИКА документооборота пятеркой , где . При этом каждое состояние ИКА представляет подмножество .

3.4.2. Архитектура ИКА

В работе [10] показано, что рекурсивные алгоритмы могут быть построены из иерархических модулей, которые вызывают сами себя и рекурсивно передают входные и выходные данные. На рисунке 2 показана рекурсивная функция gcd. Локальные состояния x1 и x2 определяют соответствующую ветвь алгоритма. Микрооперации y1 и y2 осуществляют обработку данных и рекурсивную передачу данных между модулями алгоритма. Рекурсия организуется путем многократного вызова одного модуля, в нашем случае модуля Z.

НачалоКонецZif (B>A)if(B==0) 100

Рис. 2. Рекурсивная функция gcd

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

M_StackFSM_StackсинхромодульНовый модульСледующее состояниеТекущий модульТекущее состояние#Управляющие воздействия: clock, reset, push (#), pop (&)Z#**

Рис. 3. Архитектура ИКА.

Иерархический КА, который приведен на рис. 3, имеет два технологических стека. Один стек автомата, который обозначен FSM_stack, предназначен для обработки состояний. Второй стек, обозначенный M_stack, предназначен для обработки модулей, представляющих собой автоматы моделирования поведенческих единиц.

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

Состояние внутри ИКА соответствует состояниям a0…a4 на рис. 1. Поскольку каждый конкретный модуль имеет уникальный идентификатор, то обозначения одних и тех же состояний могут использоваться в различных модулях. На рис. 2 показано, как ИКА исполняет алгоритм, приведенный на рис. 1.

Все неиерархические вызовы производятся путем смены кода модуля в верхнем состоянии регистра FSM_Stack. На рис. 2 такой пример обозначен знаком «*». Все иерархические вызовы изменяют состояния обоих стеков. При этом M_Stack сохраняет код нового модуля, а FSM_Stack устанавливается в начальное состояние инициализируемого модуля. Такой пример на рисунке 2 обозначен символом «#».

Иерархический вызов активирует операцию «pop» без изменения стеков, на рисунке это обозначено «&». В результате завершения работы модуля ИКА перейдет в состояние, последующее за состоянием, на котором был произведен вызов модуля. Указатель стеков stack_ptr является общим для обоих стеков. Работа ИКА прекращается при достижении позиции «End» и состоянии указателя stack_ptr =0.

Характеристики

Список файлов статьи