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

     Определение эквивалентного разбиения событий для построения
минимального ЦА Мура.
     В том случае, если требуется построить минимальный ЦА Мура, то для
определения эквивалентного разбиения событий, как было отмечено ранее,
необходимо по исходной ПТП ЦА Мура (табл.3.1) найти все классы 0-
эквивалентных событий, которые будут использованы для построения
основного столбца таблицы пар.
     Дальнейшая методика построения таблицы пар для автомата Мура
ничем не отличается от рассмотренной методики для автомата Мили.
     Для нашего примера таблица пар для определения эквивалентного
разбиения событий для построения минимального ЦА Мура будет иметь
следующий вид (табл.3.3).
                                                             Таблица 3.3
  Классы 0-             Пары
 эквивалент-        0-эквивалент-   x1 x2   x1 x2   x1    x3        x3       1
 ных событий        ных событий
                         1           2       3       4     5        6        7
   S 1, S 4 , S 8       1-4         3-6     3-7     2-5                             1
                        1-8         3-7     3-7     2,5                             2
                        4-8         6-7     7-7     5,5                             3
     S 2 , S5           2-5                                                 3-8     4
   S 3, S 6 , S 7       3-6                               4-9     4-10              5
                        3-7                               4-9     4-10              6
                        3-7                               9-9    10-10              7

      На первом шаге алгоритма отыскания эквивалентного разбиения
событий находим пары (3-8) (4-9), которые отсутствуют в основном столбце.
Для таких пар зачеркиваются соответствующие им пары в основном столбце,
к ним относятся пары: (2-5), (3-6), (3-7).
      На втором шаге алгоритма отыскиваются строки, в которых имеются
пары, зачеркнутые в основном столбце на первом шаге алгоритма. Для
нашего примера это строки 1-я и 2-я, для них зачеркиваются пары (1-4) и (1-
8).
      Для нашего примера на этом шаге алгоритма отыскания
эквивалентного разбиения событий свою работу заканчивает, так как больше
не обнаруживаются невыделенные строки, в которых имеются пары,
зачеркнутые в основном столбце на предыдущем шаге алгоритма.
Оставшиеся незачеркнутые пары событий образуют пары эквивалентных
событий, к ним относятся пары: S 4 , S 8  и S 6 , S 7  .
      Учитывая состав событий, которые не вошли в пары эквивалентных
событий, получим следующее эквивалентное разбиение событий для ЦА
Мура для нашего примера:
      S 0, S1, S 2, S 3, S 4 , S 8, S 6 , S 7 , S 9 , S k , S 5, S10 .
                                                                                        50