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

прямой таблицы переходов должно начинаться с исходного начального
события. При этом очередное событие может быть занесено в первый
столбец таблицы в качестве исходного только в том случае, если оно имело
место в один из предшествующих шагов алгоритма работы автомата (было
зафиксировано в качестве события перехода). Указанная процедура
построения прямой таблицы переходов позволит избавиться от всех
недостижимых событий. В то же время такая таблица является и исходной
информацией для выполнения последующих основных этапов минимизации
СКУ.


      3.1. Минимизация СКУ на основе определения
            эквивалентного разбиения событий
             3.1.1. Некоторые понятия и определения

      Для минимизации числа событий СКУ можно воспользоваться одним
из методов, предложенных для минимизации числа состояний автомата,
заданного классической таблицей переходов и выходов, основанного на
определении эквивалентного разбиения автомата [27]. При использовании
таких методов возникает необходимость в их коррекции, которая
обусловлена применением частных входных сигналов при описании
событий. Прежде чем приступить к рассмотрению методики определения
эквивалентного разбиения автомата, введем некоторые понятия и
определения, полезные при дальнейшем рассмотрении вопросов
минимизации СКУ. Эти понятия и определения базируются на
заимствовании аналогичных понятий, применительно к минимизации
внутренних состояний автомата [27].
      Эквивалентность событий. События S и S эквивалентны, если при
переходе из них под воздействием любой входной последовательности
сигналов, формируются одинаковые выходные последовательности сигналов.
Эквивалентность событий S и S будем обозначать равенством S=S.
Отношения эквивалентности обладают свойствами: рефлексивности (S=S),
симметричности (если S=S, то S=S) и свойством транзитивности (если
S=S и S=S, то S=S ).
      K-эквивалентность событий. События S и S k-эквивалентны, если
при переходе из них под воздействием любой входной последовательности
сигналов длины k, формируются одинаковые выходные последовательности
сигналов. Если события S и S не являются k-эквивалентными, то они
называются k-различимыми.
      Преемники (или последователи) событий. К-м преемником события
S по отношению к входной последовательности сигналов длины k называют
событие, которое формируется из события S под воздействием входной
последовательности сигналов длины k.
                                                                      44