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

      Определение эквивалентности одних событий при установленной
эквивалентности других событий.
      а) Если события S и S являются k-эквивалентными и если их k-е
преемники по отношению к любой входной последовательности сигналов
длины k являются эквивалентными, то S=S. С другой стороны, можно
утверждать, что, если события S и S являются k-эквивалентными, а их k-e
преемники по отношению к любой входной последовательности сигналов
длины k являются k-различимыми, то SS.
      б) Если события S и S являются эквивалентными, то их k-e преемники
по отношению к любой входной последовательности сигналов длины k и для
любого k являются эквивалентными.
      К-эквивалентное разбиение событий СКУ на классы.
      Все множество событий может быть разбито на классы по признакам:
      а) Все события, принадлежащие одному классу, должны быть k-
эквивалентны, их называют также смежными.
      б) Все события, принадлежащие к различным классам, должны быть k-
различимыми.
      Такое разбиение называют k-эквивалентным разбиением событий СКУ.
      Эквивалентные разбиения событий СКУ. Эквивалентным
разбиением событий СКУ называется k-эквивалентное разбиение их, когда в
каждом из классов этого разбиения смежные события эквивалентны. Такое
разбиение в принципе может быть получено, если последовательно получать
k-эквивалентные разбиения событий, начиная с k=1 для автомата Мили и k=0
для автомата Мура. Такие разбиения последовательно получают до тех пор,
пока первый раз не получается разбиение, которое совпадает с предыдущим.
Это разбиение событий СКУ и будет эквивалентным разбиением. Для
определения такого разбиения событий могут быть использованы различные
методы. Рассмотрим один из них, который основан на использовании так
называемой таблицы пар [27].

        3.1.2. Определение эквивалентного разбиения событий
               СКУ на основе использования таблицы пар

       Такое разбиение выполняется последовательным изменением таблицы
пар путем вычеркивания по определенному алгоритму тех пар событий,
которые не являются эквивалентными. Оставшиеся не вычеркнутые пары
будут образовывать все пары эквивалентных событий.
       Методику построения таблицы пар и ее использования для
определения эквивалентного разбиения событий СКУ будем рассматривать
на основе примера автомата Мура, заданного прямой таблицей переходов
(табл. 3.1), в которой все события как исходные, так и события перехода,
отмечены выходными сигналами.

                                                                        45