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

алгоритму, который, как было отмечено ранее, базируется на алгоритме
синтеза цифровых автоматов Мура, преложенном в [12].
             2.1. Алгоритм детерминизации НДА
      Алгоритм построения прямой таблицы переходов детерминированного
автомата Мура включает следующие этапы:
      1) Строится прямая таблица переходов НДА Мура и заготавливается
прямая таблица переходов детерминированного автомата Мура. По прямой
таблице переходов исходного НДА (ПТП НДА) отыскивается совокупность
(сочетание) исходных — начальных событий и/или частных событий,
выводимых из них. Этой совокупности (сочетанию) начальных событий,
ставится в соответствие начальное состояние детерминированного автомата,
а их обозначения записываются во второй столбец в первой строке прямой
таблицы переходов детерминированного автомата Мура (ПТП ДА Мура).
      2) Для каждого исходного (вначале начального) частного события,
входящего в совокупность (сочетание) частных событий, записанных во
втором столбце ПТП ДА Мура, выписываются в третий столбец
подмножества частных входных сигналов, которые вызывают переходы из
этих исходных событий.
      В каждом из подмножеств частных входных сигналов находят все не
эквивалентные между собой и не эквивалентные нулю сочетания.
      3) Выполняют анализ и корректировку состава каждого из полученных
подмножеств сочетаний частных входных сигналов, вызывающих переходы
из исходного события, на основании которого:
      а) оставляют для дальнейшего рассмотрения сочетания, не являющиеся
выводимыми ни из какого одного из сочетаний рассматриваемого
подмножества и те из выводимых, для которых их истинность не влечет
истинность хотя бы одного из сочетаний, из которого это сочетание само
выводимо;
      б) исключают из дальнейшего рассмотрения те из выводимых
сочетаний частных входных сигналов рассматриваемого подмножества,
истинность которых всегда влечет истинность хотя бы одного из сочетаний,
из которых они выводимы;
      в) выполняют проверку состава частных входных сигналов
рассматриваемого подмножества на полноту состава. Нарушение полноты
состава частных входных сигналов будет иметь место в том случае, если
логическая сумма всех частных входных сигналов данного подмножества не
равна единице. Такой состав частных входных сигналов не удовлетворяет
условиям полноты переходов в автомате для рассматриваемого исходного
события.
      Для устранения неполноты состава частных входных сигналов
определяются дополнительные частные входные сигналы, которые для
рассматриваемого подмножества будут запрещенными. Для них
                                                                      26