[ <<< | Содержание, 1, 2 | 3 - 5 | 6, 7 | 8, 9 | 10, Литература | >>> ]


Просим прощения за причиненные неудобства, связанные с исползованием шрифта Symbol

6. Задание бесповторного автомата

Определим БПСА в стиле, близком к классическому, например [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.

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

7. Автоматы со скрытыми переходами и состояниями

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

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

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

Если БПСА повторно реализуется в собственном цикле, то его переменная – состояние на все время пребывания в цикле недоступна другим программам. Поэтому переходы, соответствующие установке ФСП (в единицу) называются скрытыми. Если все переходы в некоторое состояние, в том числе петли, приводят к установке ФСП, то такое состояние называется скрытым, так как никакой другой программе данное состояние недоступно.

Для блокировки прологов и эпилогов используется простая конструкция выбора “ЕСЛИ ФСП = 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, Литература | >>> ]