[ <<< | Содержание, 1, 2 | 3 - 5 | 6, 7 | 8, 9 | 10, Литература | >>> ]
Просим прощения за причиненные неудобства, связанные с исползованием шрифта Symbol
Определим БПСА в стиле, близком к классическому, например [8]. Если БПСА задать в виде {T, S, Z, W, Y, …}, где T – входной алфавит, S – множество состояний, Z – первый выходной алфавит, и так далее, то представляет большое затруднение задать структуру элементов множества Z (прологи, эпилоги, активизирующие действия и прочее). Поэтому исключим Z из описания автомата за счет введения дополнительных множеств.
БПСА назовем систему
C = { S, T, Y, W, A, X, P, E, r, u, v, f },
где S = {S1,…,SN} – множество состояний, N – число состояний, Т = {T1,…,TL} – множество событий, L – число бесповторных событий, Y = {Y1,…,YL} – множество действий, реализуемых по соответствующим событиям, W = {W1,…,WN} – множество действий, реализуемых при отсутствии событий, инициируемых соответствующими состояниями, A = {A1,…,AL} – множество активизирующих действий для соответствующих событий, X = {X1,…,XL} – множество логических условий, отвечающих соответствующим событиям, P = {P0,P1,…,PN} – множество прологов: P0 – БПСА в целом, P1 – PN – состояний, E = {E0,E1,…,EN} – множество эпилогов (нумерация элементов аналогична P), r = {r1,…,rN} – множество старших индексов событий (см. ниже), u: S*T -> S – функция переходов, v: S*T -> Y – функция выходов, f = {f1,…,fL} – множество двоичных признаков скрытых переходов (см. ниже, раздел 7).
Каждому состоянию БПСА соответствуют инициируемые в его теле события, причем ни одно событие не инициируется более чем одним состоянием. Считаем, что события с номерами 1 – r1 инициируются состоянием S1, события с номерами r1+1 – r2 – состоянием S2, и так далее. Таким образом, элементы множества r обозначают старший номер события, инициируемого соответствующим состоянием. Отсюда следует
T_j = ~T_j-1 & [A_j -> X_j] при j-1 П r,
T_j = [A_j -> X_j] при j = 1, или j-1 О r.
В отличие от АНС задать БПСА традиционной автоматной таблицей (таблицей переходов и выходов) не представляется возможным из-за обилия взаимосвязанных компонент. Поэтому для описания БПСА предлагается использовать список событий, элемент которого соответствует одному переходу и имеет вид
<s1, p, g, x, t, f, y, s2, w, e >,
где s1,s2 О S, p О P, g О A, x О X, t О T, y О Y, w О W, e О E.
Для наглядности можно использовать и граф переходов, в котором условием на дугах указаны события без способа их получения.
Рассмотрим пример задания БПСА с четырьмя состояниями. Граф переходов БПСА изображен на рис. 4.
В состояниях a, b, c, d реализуются бинарные многополюсники, соответственно Za, Zb, Zc, Zd, формирующие события T1 – T10. Каждое событие Tj инициирует соответствующую подпрограмму Yj (j = 1,…,10). Если ни одно из событий, формируемых многополюсником какой либо вершины, не случилось, то реализуется соответствующая подпрограмма Wa (Wb, Wc, Wd).
Из рисунка следует, что из-за наличия нескольких дуг, исходящих из вершины a (d) и заходящих в одну и ту же вершину b (c), а также наличия двойных петель у вершин b и d, граф переходов является мультиграфом, что характерно для ПСА в отличие от АНС.
Граф на рис. 4 не раскрывает сути бинарных многополюсников, не показывает пролога и эпилога программы ПСА в целом. Поэтому вводится дополняющий граф переходов таблица-список событий (табл. 1). В этом списке, конкретизируется структура бинарного многополюсника, представленного на рис. 2, применительно к каждому из состояний БПСА, изображенного на рис. 4. Указанный список требует следующих пояснений.
Таблица 1.
Список событий ( дополнение к рис. 4 )
Состояние |
Пролог |
Активизирующее действие |
Логическое выражение |
Событие |
Действие на петле |
Эпилог |
s1 |
p |
g |
x |
t |
w |
e |
любое |
P0 |
- |
- |
- |
- |
E0 |
a |
P1 |
A1 |
X1 |
T1 |
- |
E1 |
- |
- |
~T1/A2 |
X2 |
T2 |
- |
- |
- |
- |
~T2/- |
- |
- |
W1 |
- |
b |
P2 |
A3 |
X3 |
T3 |
- |
E2 |
- |
- |
~T3/A4 |
X4 |
T4 |
- |
- |
- |
- |
~T4/A5 |
X5 |
T5 |
- |
- |
- |
- |
~T5/- |
- |
- |
W2 |
- |
d |
P3 |
A6 |
X6 |
T6 |
- |
E3 |
- |
- |
~T6/A7 |
X7 |
T7 |
- |
- |
- |
- |
~T7/A8 |
X8 |
T8 |
- |
- |
- |
- |
~T8/- |
- |
- |
W3 |
- |
c |
P4 |
A9 |
X9 |
T9 |
- |
E4 |
- |
- |
~T9/A10 |
X10 |
T10 |
- |
- |
- |
- |
~T10/- |
- |
- |
W4 |
- |
В графе “s1” указывается текущее состояние БПСА. В графах “p” и “e” задаются действия прологи и эпилоги, соответственно. При этом выделяется отдельная строка (первая) таблицы-списка для указания пролога P0 и эпилога E0, общих для БПСА в целом.
В графе “g” показаны активизирующие действия из многополюсника, причем для части из них указаны условия реализации в виде отрицания события, которое не наступило при проверке истинности логического выражения, указанного в предшествующей строке. Например, выражение ~T1/A2 обозначает: если событие T1 не наступило, то выполнить подпрограмму А2 и далее проверить истинность логического выражения X2 из соседней справа графы той же строки списка. Таким образом, каждое событие возможно только при невыполнении предыдущего события.
Состояния (“s2”) переходов и действия (“y”) на дугах (кроме действий (“w”) на петле) из-за ограниченности формата страницы в табл. 1 не представлены.
Действие (“w”) на петле, например, W1 реализуется только в том случае, если ни одно из указанных для состояния “a” событие не произошло. (На рис. 4 указаны и такие петли, которые реализуют оговоренные события, например, Т5 и Т8.)
Конечно, возможно обойтись и без списка событий, если в БПСА нет прологов и эпилогов. При этом следовало бы вводить специальные отметки на дугах переходов, например, вида
[ T2 = [ ~T1 / A2 -> X2 ]] / Y2,
смысл которой несложно раскрыть, используя рис. 4 и табл. 1.
Таким образом, основное отличие БПСА от АНС состоит в наличии активизирующих действий и механизма отрицания событий, а также прологов и эпилогов, что требует табличного способа задания БПСА при необязательном задании графа переходов.
Рассмотренные БПСА и АНС как подпрограммы реализуют только один переход, после чего передают управление программе более высокого уровня и повторно вызываются для реализации следующего перехода. Поэтому временной интервал между соседними переходами исчисляется не только временем реализации автомата, но и временем работы вызывающей программы.
В ряде случаев необходимо продолжить выполнение переходов не выходя из тела подпрограммы БПСА. Такая ситуация возникает при необходимости соблюдения определенного быстродействия подпрограммы БПСА или при необходимости продолжать вычисления с не возобновляемыми данными. Для реализации таких случаев предлагается механизм скрытых переходов и скрытых состояний.
Суть данного механизма состоит в том, что некоторый переход приводит не к завершению подпрограммы БПСА, а к возврату в ее начало. При этом может быть заблокировано выполнение прологов и эпилогов. Для реализации такого процесса в БПСА вводится флаг скрытого перехода (ФСП). При наступлении некоторых заданных событий ФСП принимает единичное значение, а при наступлении остальных событий ФСП обнуляется. Перед завершением подпрограммы БПСА проверяется ФСП, и, если он не нулевой, то выполняется возврат к началу подпрограммы БПСА. Другими словами подпрограмма БПСА, содержащая ФСП, имеет собственный цикл.
Если БПСА повторно реализуется в собственном цикле, то его переменная – состояние на все время пребывания в цикле недоступна другим программам. Поэтому переходы, соответствующие установке ФСП (в единицу) называются скрытыми. Если все переходы в некоторое состояние, в том числе петли, приводят к установке ФСП, то такое состояние называется скрытым, так как никакой другой программе данное состояние недоступно.
Для блокировки прологов и эпилогов используется простая конструкция выбора “ЕСЛИ ФСП = 0 ТО Pi (Ei)”.
Скрытые переходы на графе переходов обозначаются перечеркиванием соответствующей дуги [9]. Так, например, граф переходов, изображенный на рис. 5 содержит скрытые переходы по событиям Т1, Т2, Т3, Т5, а также скрытую петлю у вершины b.
Этот граф содержит скрытое состояние b. В граф-схемах явно указывается установка, сброс и проверка ФСП. На рис. 6, 7 показаны соответствующие фрагменты БПСА, реализующего граф переходов (рис. 5). В списках событий ФСП упоминается в графах “p”, “t”, “e”. В таблице 2, задающей события для БПСА по рис. 5, символом F обозначен ФСП.
Как следует из рис. 6, сокрытие переходов и состояний обеспечивается собственным циклом подпрограммы БПСА, обеспечиваемым не нулевым значением ФСП, устанавливаемым в блоках реализации состояний и событий, например, согласно рис. 7. Подпрограмма возвращает управление вызвавшей ее программе только в том случае, когда ФСП установлен в ноль.
Таблица 2.
Список событий и ФСП ( дополнение к рис. 5 )
Состояние |
Пролог |
Активизирующее действие |
Логическое выражение |
Событие и ФСП |
Действие на петле |
Эпилог |
s1 |
p |
g |
x |
t, f |
w |
e |
любое |
~F/P0 |
- |
- |
- |
- |
~F/E0 |
a |
P1 |
A1 |
X1 |
T1, F=1 |
- |
E1 |
- |
- |
~T1/A2 |
X2 |
T2, F=1 |
- |
- |
- |
- |
~T2/- |
- |
F=0 |
W1 |
- |
c |
P3 |
A3 |
X3 |
T3, F=1 |
- |
E3 |
- |
- |
~T3/- |
- |
F=0 |
W3 |
- |
b |
P2 |
A4 |
X4 |
T4, F=0 |
- |
E2 |
- |
- |
~T4/- |
- |
F=1 |
W2 |
- |
d |
P4 |
A5 |
X5 |
T5, F=1 |
- |
E4 |
- |
- |
~T5/A6 |
X6 |
T6, F=0 |
- |
- |
- |
- |
~T6/- |
- |
F=0 |
W4 |
- |
Установка и проверка ФСП могут отличаться от приведенного примера, но основная цель – сокрытие переходов в цикле должна быть достигнута. БПСА может содержать более одного ФСП, например, скрытое состояние может иметь собственный ФСП для блокирования в цикле его пролога и эпилога и даже активизирующих действий.
[ <<< | Содержание, 1, 2 | 3 - 5 | 6, 7 | 8, 9 | 10, Литература | >>> ]