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

называют свернутой формой, а выражение (1.3) – развернутой формой
определенного регулярного выражения алгебры событий.
     В связи с этим каждую предикатную формулу S j (t  1) системы (1.1)
можно привести к следующей свернутой форме регулярного выражения,
имеющего вид:
       S j (t )  V S i (t  1) & X i, j (t )  V S j (t  1) & X j , j (t ) 
               i, j                                            j
                                                                                               (1.4)
              V S i X i , j  V S j X j , j  V S i X i, j { X j , j}
                i, j                  j                            i, j

      Выполняя все необходимые операции свертывания в уравнениях
системы (1.1), которые содержат вторую часть описания, определяющую
условия сохранения события, и выполняя m-раз операции подстановки
свернутых выражений вместо непосредственно предшествующих событий S i
в выражения типа (1.4), получим представление исходной системы (1.1) в
виде выражений алгебры событий, выраженные через частные входные
сигналы и начальное событие S 0 с использованием только 3-х операций
алгебры событий: дизъюнкции, конкатенации и итерации.
      Таким образом, учитывая изложенное, можно утверждать, что система
уравнений (1.1), представляющая простую каноническую форму,
описывающая все реализуемые в автомате частные события, на основании
теоремы С.К.Клини представима в конечном цифровом автомате, а
следовательно и в НДА.
      Примечание. В главе 4, посвященной начальным языкам, будет подробно
рассмотрен алгоритм преобразования регулярных выражений алгебры событий в
описание событий в виде системы канонических уравнений.
      Для построения управляющего автомата в виде модели автомата Мура
необходимо, кроме функций переходов, представленных уравнениями (1.1),
получить и систему выходных функций (СВФ). Она может быть получена из
(1.I) путем объединения тех событий Sj , в состав отмеченных частных
выходных сигналов которых входит рассматриваемый элементарный
выходной сигнал, т. е. СВФ для автомата Мура будет иметь вид
                                                                   Yj
                       y k (t  1)          V Sj
                                          S Y  y 
                                                                          (t  1) , k  1,N            (1.5)
                                               j   j   k

или
                                                 Y
                       y k (t )       V
                                    S Y  y 
                                                S j (t ), k  1, N ,
                                                           j                                  (1.6)
                                      j    j       k

где переменные в левой и правой частях уравнений взяты для одного и того
же момента времени.
      Система выходных функций для модели автомата Мили
эквивалентного ему автомата Мура, может быть получена из отмеченной НД
СКУ вида (1.1) путем объединения выражений для тех событий Sj, в состав
отмеченных частных выходных сигналов которых входит рассматриваемый
                                                                                                               15