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

UptoLike

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

23
Покажем на примере взаимосвязь между отдельными видами
запрещенных входных сигналов и пустым входным сигналом.
Пусть алфавит абстрактных входных сигналов содержит следующие
пять сигналов
]
,
,
,
,
[
]
[
43210
z
z
z
z
z
Z
. Тогда при построении структурной
схемы автомата абстрактные входные сигналы должны кодироваться тремя
двоичными входными сигналами из алфавита
]
,
,
[
]
[
321
xxx
X
.
Для произвольного кодирования получаем.
,
,
,
3
2
1
2
3
21
1
321
0
x
x
x
x
xx
xxx
z
z
z
.
,
32
1
4
32
1
3
xx
x
xx
x
z
z
Неиспользуемые кодовые группы имеют вид:
32
15
xx
x
z
,
,
3
216
x
xx
z
xxx
z
3217
.
Эти неиспользуемые кодовые группы и составят полные запрещенные
входные сигналы. Они определятся также как отрицание от дизъюнкции
действующих входных сигналов:
xxx
x
xxx
x
x
zzzzz
е
321
3
213
2
1
43210
З
.
Пустой абстрактный входной сигнал для данного алфавита входных
сигналов определится как отрицание от дизъюнкции всех абстрактных
входных сигналов, включая запрещенные:
01
З
43210
е
е
zzzzz
S-событие это частное событие, определяемое частными входными
сигналами, отмеченное соответствующей совокупностью выходных сигналов
из алфавита [Y] и формализуемое в соответствии с формулами (1.1) и (1.12).
Множество S-событий определяет функции переходов в НДА Мура.
a-событие это полное событие, определяемое полными входными
сигналами в алфавите [X], которому соответствует возможное сочетание
частных событий, одновременное существование которых в автомате
возможно. Этому сочетанию частных событий ставится в соответствие одно
вполне определенное состояние ДА Мура, отмеченное совокупностью
выходных сигналов, отмечающих соответствующие частные события.
Множество a-событий определяют функции переходов ДА Мура.
Q-событие это событие, определяющее переходы элементарного
автомата (триггера), входящего в состав памяти автомата. Модель автомата,
представленная системой уравнений для Q-событий (СКУ для Q-событий),
будет недетерминированной относительно Q-событий, хотя система,
полученная в результате кодирования полных a-событий, представляет
реальный ДА. Отметим, что детерминизация СКУ для Q-событий даст нам
СКУ для а-событий.
     Покажем на примере взаимосвязь между отдельными видами
запрещенных входных сигналов и пустым входным сигналом.
     Пусть алфавит абстрактных входных сигналов содержит следующие
пять сигналов [ Z ]  [ z 0 , z1 , z 2 , z3 , z4] . Тогда при построении структурной
схемы автомата абстрактные входные сигналы должны кодироваться тремя
двоичными входными сигналами из алфавита [ X ]  [ x1 , x2 , x3] .
     Для произвольного кодирования получаем.
                     z 0  x1 x2 x3 ,
                                                           z3  x1 x2 x3 ,
                     z1  x1 x2 x3 ,
                                                           z 4  x1 x2 x3 .
                     z 2  x1 x2 x3 ,
     Неиспользуемые кодовые группы имеют вид:
      z5  x1 x2 x3 , z 6  x1 x 2 x3 , z 7  x1 x2 x3 .
     Эти неиспользуемые кодовые группы и составят полные запрещенные
входные сигналы. Они определятся также как отрицание от дизъюнкции
действующих входных сигналов:
               еЗ  z0  z1  z2  z3  z4  x1 x2 x3  x1 x2 x3  x1 x2 x3 .
     Пустой абстрактный входной сигнал для данного алфавита входных
сигналов определится как отрицание от дизъюнкции всех абстрактных
входных сигналов, включая запрещенные:
                       е z 0  z1  z 2  z3  z 4  еЗ  1  0
      S-событие — это частное событие, определяемое частными входными
сигналами, отмеченное соответствующей совокупностью выходных сигналов
из алфавита [Y] и формализуемое в соответствии с формулами (1.1) и (1.12).
Множество S-событий определяет функции переходов в НДА Мура.
      a-событие — это полное событие, определяемое полными входными
сигналами в алфавите [X], которому соответствует возможное сочетание
частных событий, одновременное существование которых в автомате
возможно. Этому сочетанию частных событий ставится в соответствие одно
вполне определенное состояние ДА Мура, отмеченное совокупностью
выходных сигналов, отмечающих соответствующие частные события.
Множество a-событий определяют функции переходов ДА Мура.
      Q-событие — это событие, определяющее переходы элементарного
автомата (триггера), входящего в состав памяти автомата. Модель автомата,
представленная системой уравнений для Q-событий (СКУ для Q-событий),
будет недетерминированной относительно Q-событий, хотя система,
полученная в результате кодирования полных a-событий, представляет
реальный ДА. Отметим, что детерминизация СКУ для Q-событий даст нам
СКУ для а-событий.




                                                                                  23