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

 Глава 2. Детерминизация недетерминированных
                   автоматов
      В предыдущей главе было отмечено, что над НДА возможно
выполнение большого количества операций, основными из которых
являются операции детерминизации, минимизации и кодирования. Эти
операции над НДА рассматриваются как операции над системами
канонических уравнений (СКУ), описывающими поведение НДА.
Перечисленные основные операции над СКУ и некоторые дополнительные
используются для эквивалентных преобразований НДА с целью построения
структур    управляющих     автоматов,   удовлетворяющих    заданным
определенным требованиям.
      Будем рассматривать алгоритм детерминизации НДА Мура, имея в
виду, что для НДА Мили алгоритм детерминизации в принципе будет такой
же.
      Максимально возможное число состояний детерминированного
автомата, полученного в результате детерминизации эквивалентного ему
НДА, представленного m частными событиями, не может быть больше, чем
2m и определится из выражения:
                             m
                       M   Cmk  2 m                          (2.1)
                            k 0

где Cmk — число сочетаний из m элементов по k.
      Величина М может быть определена так же, как определяется в
булевой алгебре максимальное число наборов значений двоичных
переменных, на которых задается булева функция m переменных. В нашем
случае под булевыми переменными будем понимать сокращенные
обозначения частных событий S j , число которых равно m. Если каждому
набору значений переменных Sj будет соответствовать состояние
детерминированного автомата, то M  2 m .
      Основу алгоритма детерминизации НД СКУ составляет процесс
отыскания на каждом шаге работы алгоритма функционирования автомата
множества сочетаний частных событий, одновременное существование
которых в автомате возможно. Такому сочетанию частных событий,
названному в главе 1 полным событием (a-событием), ставится в
соответствие вполне определенное состояние детерминированного автомата,
отмеченное     совокупностью     выходных      сигналов,   отмечающих
соответствующие частные события.
      Для более эффективного решения задачи детерминизации НДА более
наглядного представления этого процесса исходную НД СКУ целесообразно
представить в виде прямой таблицы переходов НДА, на основании которой
будем строить таблицу переходов детерминированного автомата по

                                                                        25