Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 90 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

90
3) Любой вход соединяется по крайней мере с одним выходом.
4) Для любой вершины графа существует по крайней мере один путь из
этой вершины к конечной вершине.
5) Один из выходов условной вершины может соединяться с ее входом,
что не допустимо для операторной вершины. В случае соединения выхода
условной вершины с ее входом в цепь обратной связи вводится пустая
операторная вершина, отмеченная пустым выходным сигналом
e
y
.
Рис. 4.3. Граф-схема алгоритма произвольного автомата
Рассмотрим выполнение алгоритма по ГСА, представленной на рис.4.3.
Выполнение алгоритма начинается с оператора
0
A
. На следующих двух
шагах выполняется последовательно операторы
1
A
и
2
A
. На четвертом шаге
может выполняться или один из трех операторов
3
A
,
4
A
и
k
A
, или
выполняется пустой оператор
e
A
в зависимости от значений логических
условий
1
x
,
2
x
и
3
x
. Если
0
21
xx
, то независимо от значения сигнала
3
x
будет выполняться пустой оператор
e
A
, т.е. автомат будет находиться в
режиме ожидания, выдавать пустой сигнал
e
y
, до тех пор, пока или
1
x
или
2
x
не станут равными единице. Если
1
21
xx
, то выполняется оператор
3
A
,
если
1
1
x
, то выполняется или
4
A
при
1
3
x
, или
3
A
при
0
3
x
.
Предположим, что после выполнения
2
A
имеет место
1
21
xx
. Тогда
независимо от значения
3
x
будут последовательно выполняться
2
A
и
3
A
столько раз, пока после очередного выполнения оператора
2
A
и проверки
0
1
1
1
0
0
0
A
0
(
y
0
)
1
A
1
(y
1
)
2
A
2
(y
2
)
1
2
3
A
e
(y
e
)
4
A
3
(y
3
)
3
5
A
4
(y
1
y
2
)
7
A
3
(y
3
)
6
A
k
(
y
k
)
       3) Любой вход соединяется по крайней мере с одним выходом.
      4) Для любой вершины графа существует по крайней мере один путь из
этой вершины к конечной вершине.
      5) Один из выходов условной вершины может соединяться с ее входом,
что не допустимо для операторной вершины. В случае соединения выхода
условной вершины с ее входом в цепь обратной связи вводится пустая
операторная вершина, отмеченная пустым выходным сигналом y e .
                               0
                               A0(y0)
                               1
                               A1(y1)
                               2
                               A2(y2)

                3
                                         1
                 Ae(ye)            x1
                                    0

                          0                              0
                                   x2            x3
                                    1             1
                               4             5               7
                               A3(y3)        A4(y1 y2)       A3(y3)

                               6
                               Ak(yk)

           Рис. 4.3. Граф-схема алгоритма произвольного автомата

       Рассмотрим выполнение алгоритма по ГСА, представленной на рис.4.3.
Выполнение алгоритма начинается с оператора A0 . На следующих двух
шагах выполняется последовательно операторы A1 и A2 . На четвертом шаге
может выполняться или один из трех операторов A3 , A4 и Ak , или
выполняется пустой оператор Ae в зависимости от значений логических
условий x1 , x 2 и x3 . Если x1  x 2  0 , то независимо от значения сигнала x3
будет выполняться пустой оператор Ae , т.е. автомат будет находиться в
режиме ожидания, выдавать пустой сигнал y e , до тех пор, пока или x1 или
x 2 не станут равными единице. Если x1  x2  1 , то выполняется оператор A3 ,
если x1  1 , то выполняется или A4 при x3  1 , или A3 при x3  0 .
Предположим, что после выполнения A2 имеет место x1  x2  1 . Тогда
независимо от значения x3 будут последовательно выполняться A2 и A3
столько раз, пока после очередного выполнения оператора A2 и проверки
                                                                              90

Страницы