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

(вначале начального) события. Этой совокупности (сочетанию) частных
событий ставится в соответствие определенное состояние ДА (полное
событие a S ), а их обозначения записываются в четвертом столбце таблицы
переходов ДА.
      В том случае, если на данном шаге работы автомата в какой-либо
строке ПТП ДА имеет место запрещенный входной сигнал, то в четвертом
столбце в рассматриваемой строке ставится черточка (или событие S ( ) ),
означающая, что событие или совокупность событий (полное событие) на
этом переходе является неопределенным.
      Если для какого-нибудь сочетания частных входных сигналов (полного
входного сигнала) и для исходных частных событий, входящих в
рассматриваемую совокупность, невыводимо ни одно из частных событий
НДА, то четвертый столбец в рассматриваемой строке отмечается
обозначением пустого события S*.
      7) Каждое из полученных новых сочетаний частных событий (полное
событие) записывается во второй столбец очередной строки таблицы
переходов автомата и вновь повторяются этапы по п.п. 2, 3, 4, 5, 6, 7 до тех
пор, пока не будут исчерпаны все новые сочетания частных событий,
записываемые в четвертый столбец.
      8) Отмечаются все совокупности (сочетания) частных событий (полные
события) соответствующими обозначениями частных выходных сигналов.
      Сочетания частных промежуточных событий (состояния автомата),
которые не отмечены никакими выходными сигналами, отмечаются знаком (
). Так как знак ( ) не противоречит никакому частному выходному сигналу,
то при необходимости можно дополнительно отметить эти состояния ДА
любым (в том числе и пустым) выходным сигналом.
      9)После окончания построения ПТП ДА ее еще раз проверяют на
однозначность и полноту переходов. Для однозначности переходов должно
выполняться условие равенства нулю всех попарных произведений входных
сигналов на каждом шаге работы алгоритма ДА, а для полноты переходов
логическая сума всех полных входных сигналов на каждом шаге работы
алгоритма ДА должна равняться единице.
      По полученной прямой таблице переходов детерминированного
автомата Мура нетрудно построить детерминированную СКУ по
следующему алгоритму:
      1) В прямой таблице переходов, полученной после детерминизации,
отыскиваются все пути, которые оканчиваются одинаковыми полными
событиями (состояниями) as(t +1), и составляются для них конъюнкции из
обозначений полных событий (состояний) am(t), стоящих в начале пути
перехода, с соответствующими сочетаниями частных входных Х(am, as)
сигналов, действующих на переходе от am к as.


                                                                          28