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

      При формализации частных событий системы (1.12) необходимо иметь
в виду, что описание каждого частного события S j должно в общем случае
состоять из трех частей [21]:
           описание события в момент его наступления;
           описание условий, при которых событие сохраняется;
           описание события, непосредственно предшествующего событию
Sj.
      Отметим также, что описание некоторых событий могут и не иметь
описаний условий его сохранения, тогда как две другие части описания
события S j должны быть обязательно. В противном случае описание
события S j может преобразоваться в булеву функцию, реализуемую простой
комбинационной схемой.
      Полученная система уравнений (1.12) должна быть проверена на
отсутствие недостижимых событий. Для этой цели строится прямая таблица
переходов недетерминированного автомата Мура (НД ПТП) для всех
частных событий, представленных уравнениями (1.12) и реализуемых в
автомате.
      НД ПТП Мура в общем случае может иметь пять основных колонок
(рис.1.2).

               S i (t )    Ri (t )    X i , j (t )   S j (t  1)   Y j (t  1)
        1        2           3            4              5             6
       1        S0

              Рис.1.2. Прямая таблица переходов для событий
                           НДА Мура (НД ПТП)

      Построение НД ПТП должно выполняться по следующему правилу:
построение первой строки таблицы начинается с исходного события S i ,
которое соответствует событию S 0 , а для всех последующих строк в качестве
исходного события S i используется то, которым уже была отмечена колонка
(5) в предыдущих строках таблицы. Такой порядок построения НД ПТП
выявляет недостижимые события, то есть те, которые не имеют событий
предшественников.
      Построенная НД ПТП может быть в дальнейшем использована для
преобразования системы уравнений (1.12), связанных с выполнением
операций минимизации, детерминизации, кодирования и др.
      Отличительными особенностями языка НД СКУ являются:
      а) Язык НД СКУ является языком, определяющим в явном виде
функции переходов в автомате. Эти функции выражаются в виде переходов
от события к событию (или событиям) или переходов от событий к событию
                                                                                 19