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

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

47
Продолжение таблицы 3.1
Шаг
алгоритма
Исходное
событие
)
)(
(
Y
t
S
i
i
Входной сигнал
)
(
,
t
X
ji
Событие
перехода
)
)(
1
(
Y
t
S
j
j
8
y
S
3
7
3
3
x
x
y
S
y
S
5
10
4
9
9
y
S
1
8
x
x
1
1
y
S
y
S
3
7
2
5
10
y
S
4
9
1
y
S
k
k
11
y
S
5
10
3
3
x
x
y
S
y
S
5
10
4
9
Такое представление исходной прямой таблицы переходов ЦА Мура
позволит использовать ее для построения таблицы пар при определении
эквивалентного разбиения событий как для ЦА Мура, так и для
эквивалентного ему автомата Мили. Разница будет заключаться лишь в
построении основного столбца таблицы пар: для автомата Мура в основном
столбце размещают все пары 0-эквивалентных событий S
и S
(для ), а
для автомата Мили — все пары 1-эквивалентных событий.
Напомним, что под 0-эквивалентными событиями понимаются те
события, которые отмечены во втором столбце прямой таблицы переходов
одинаковыми выходными сигналами, а под 1-эквивалентными событиями
понимают события (во втором столбце), при переходе из которых под
действием одного и того же входного сигнала формируются одинаковые
выходные сигналы (в четвертом столбце).
Для нашего примера имеются три класса 0-эквивалентных событий:
(S
1
, S
4
, S
8
), (S
2
, S
5
), (S
3
, S
6
, S
7
) и три класса 1-эквивалентных событий: (S
1
, S
4
,
S
8
), (S
0
, S
3
, S
5
), (S
6
, S
7
, S
10
).
Определение эквивалентного разбиения событий для построения
минимального ЦА Мили.
Рассматриваемая методика определения эквивалентного разбиения
событий на основе использования ПТП ЦА Мура позволяет, наряду с
процедурой минимизации числа событий, выполнить также и одновременное
преобразование автомата Мура в эквивалентный ему автомат Мили с
минимальным числом событий.
Для более компактного представления таблицы пар ее целесообразно
представлять в виде подтаблиц, число которых определится для ЦА Мили
числом классов 1-эквивалентных событий.
Как было отмечено выше, для автомата Мили основной столбец
таблицы пар будет содержать все пары 1-эквивалентных событий. Во все 
                                                       Продолжение таблицы 3.1
      Шаг             Исходное          Входной сигнал          Событие
   алгоритма          событие               X i, j (t )         перехода
                      S i (t )(Y i )                           S j (t  1)(Y j )
        8              S 7  y 3              x3                  S 9 y 4
                                               x3                 S 10  y 5 
        9               S 8  y1              x1                 S 5 y 2
                                               x1                 S 7  y 3
        10              S 9  y 4              1                 S k y k 
        11              S 10  y5             x3                 S 9 y 4
                                               x3                 S 10  y 5 

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

                                                                                   47

Страницы