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

      Таким образом, недетерминированный автомат Мура это пятерка:
                           M=S, Xi,j, , S0, Yj,
где S = [S1, S2, ..., Sm] - множество частных событий;
   [Xi,j] - множество частных входных сигналов, образуемых сочетаниями
             элементарных двоичных входных сигналов из алфавита [X;
   Yj] - множество выходных сигналов, отмечающих частные события Sj и
             образуемых совокупностью двоичных элементарных выходных
             сигналов из алфавита Y;
   S0 - начальное событие (возможно существование нескольких начальных
          событий);
    - функция переходов НДА, которую в обобщенном виде можно
         представить так:
              (Si,1, ..., Si,k), Xi,j(t)=(Sj,1, ..., Sj,l),(Yj,1, ...,Yj,l)(t+1),
откуда видно, что функция переходов  определяет переходы от i-го
множества частных событий (Si,1, ..., Si,k) к j-му множеству частных событий
(Sj,1, ..., Sj,l), одновременное существование которых в автомате возможно,
под действием частного входного сигнала Хi,j. Необходимо иметь в виду, что
в некоторых случаях i-е и/или j-е множества частных событий для отдельных
переходов могут содержать в себе только один элемент.
        Отметим, что недетерминированность модели автомата Мура
будет проявляться лишь в возможном переходе под действием входного
сигнала от какого-либо частного события Si (или событий) к нескольким
частным событиям (или событию Sj ).
     В то время как в детерминированном автомате (если под событием
понимать переход автомата в определенное состояние аj), всегда реализуются
переходы под действием сигнала Xi,j от события Si только к одному событию
Sj .
     По НДА может быть построен эквивалентный ему конечный
детерминированный автомат с помощью алгоритма детерминизации. Один из
вариантов алгоритма детерминизации был предложен в работе [12], где он
представлен    в    виде   алгоритма    синтеза    таблицы   переходов
детерминированного цифрового автомата Мура, заданного моделью НДА в
виде системы рекуррентных бескванторных предикатных формул,
описывающих все реализуемые в автомате частные события. В дальнейшей
работе 2] алгоритм детерминизации усовершенствовался применительно к
синтезу    микропрограммных     управляющих     автоматов.  Алгоритмы
детерминизации НДА были также рассмотрены, например, в работах 5, 6, 8.
     В процессе детерминизации каждому возможному множеству
одновременно возбужденных вершин (событий) ставится в соответствие

                                                                                     9