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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

14
Y
j
— частный выходной сигнал, представляющий собой сочетание
элементарных выходных сигналов из алфавита Y, отмечающих
вершину графа b
j
(или событие S
j
).
Систему уравнений вида (1.1) будем называть в дальнейшем простой
канонической формой или сокращенно — системой канонических
уравнений (СКУ). При этом, если система уравнений описывает НДА, то
сокращенное обозначение ее будет — НД СКУ. Кроме того, так как способы
представления цифровых автоматов принято называть также и языками
представления автоматов, то и в нашей работе, когда это целесообразно,
будем называть систему уравнений вида (1.1) сокращенно— язык СКУ.
Как видно из (1.1) СКУ определяет все переходы в НДА и является
отмеченной НД СКУ автомата Мура, так как каждое событие S
j
отмечено
своим частным выходным сигналом Y
j
. При этом первая часть уравнений
(1.1) позволяет формализовать описание условий первоначального появления
или зарождения события S
j
, а вторая - определить условие возобновления или
сохранения его. Следует иметь ввиду, что описание некоторых событий S
j
системы (1.1) могут и не содержать вторую часть уравнений, определяющую
сохранение события S
j
, в то время как присутствие первой части в каждом
уравнении системы (1.1) обязательно.
Из системы уравнений (1.1) также следует, что введенное понятие
«событие», принципиально ничем не отличается от понятия события,
принятого в теории конечных цифровых автоматов 1. Действительно,
следуя 1, в нашем рассмотрении событие, например, S
j
— это также
множество слов, каждое из которых состоит из последней буквы (Х
i,j
) этого
слова и начального отрезка слова до этой буквы, обозначенного сокращенно
S
i
, и определяемое как событие, непосредственно предшествующее событию
S
j
.
Представление функционирования НДА системой уравнений (1.1)
соответствует описанию, которое является результатом преобразования
регулярных выражений алгебры событий (РВАС) произвольной формы к
виду, представленному в развернутой форме в виде системы канонических
уравнений. Действительно, используя правило развертывания итерации и
закона коммутативности для итерации, в алгебре событий [1] выражение для
события вида
R
SS
,  (1.2)
преобразуется в выражение с отсутствием итерационных скобок
R
SSS
. (1.3)
Откуда следует, что выражения (1.2) и (1.3) являются различными формами
определения одного и того же события
S
. При этом выражение (1.2)

Страницы