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

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


                                                                        14