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

                                                                         Таблица 3.2
  Классы 1-             Пары
 эквивалент-        1-эквивалент-   x1 x 2   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
  S0 , S3, S5            0-3                                             1-4   4
                         0-5                                             1-8   5
                         3-5                                             4-8   6
  S 6 , S 7 , S10        6-7                               9-9   10-10         7
                        6-10                               9-9   10-10         8
                        7-10                               9-9   10-10         9

       Алгоритм нахождения эквивалентного разбиения событий будет
включать следующие этапы:
       1) Последовательно по строкам отыскиваются отличающиеся пары
событий (S и S, где ), которые отсутствуют в первом основном столбце
таблицы пар. Если в какой-либо строке имеется хотя бы одна такая пара, то в
этой строке зачеркивается пара в первом столбце. Такие строки, в которых
зачеркнуты пары в первом столбце таблицы, называют выделенными
строками. Для нашего примера это пары (3-6), (3-7), (2-5). Для них
зачеркиваем в первом столбце таблицы пары (1-4) и (1-8), они выделены в
таблице жирным шрифтом.
       2) Отыскиваются невыделенные строки, в которых имеются пары,
зачеркнутые в первом столбце на предыдущем этапе. Если такие строки
имеются, то для них зачеркиваются пары в первом столбце. Для нашего
примера это строки 4 и 5, для них зачеркиваем пары в первом столбце (0-3) и
(0-5). Такой процесс повторяется до тех пор, пока на очередном этапе не
обнаруживаются невыделенные строки, в которых имеются пары,
зачеркнутые в первом столбце на предыдущем этапе. Оставшиеся не
зачеркнутые пары образуют все пары эквивалентных событий. Для нашего
примера это пары: (S4,S8), (S3,S5), (S6,S7), (S6,S10), (S7,S10).
       Рассмотренная методика определения пар эквивалентных событий,
основанная на последовательном зачеркивании пар неэквивалентных
событий, базируется на использовании введенных ранее свойств (а) и (б) по
определению эквивалентности одних событий при установленной
эквивалентности других событий.
       Учитывая свойства транзитивности для эквивалентных событий, а
также состав событий, которые не вошли в пары эквивалентных событий,
получим для нашего примера следующее эквивалентное разбиение событий
ЦА Мили: (S0), (S1), (S2), (S3,S5), (S4,S8), (S6,S7,S10), (S9), (Sk).


                                                                                   49