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

появление буквы е на входе автомата свидетельствует о том, что на вход
автомата в действительности ничего не подается. Это нашло отражение в
законе нейтральности пустого слова: eS = Se = S.
      Запрещенный входной сигнал — сигнал, который на вход автомата
никогда не подается. Выражение для такого сигнала может быть определено
как отрицание от дизъюнкции всех входных сигналов Xi,j , действующих на
переходе. Для запрещенного входного сигнала событие перехода будет
неопределенным.
      Выражение для запрещенных входных сигналов может быть
определено как отрицание от дизъюнкции всех входных сигналов,
действующих на переходах алгоритма управления.
      В зависимости от типа математической модели автомата можно
выделить три вида запрещенных входных сигналов:
          Частный запрещенный входной сигнал в одной из ветвей
алгоритма управления на определенном его шаге в алфавите [X]. Например,
пусть задан фрагмент ПТП автомата, для которого не выполняются условия
полноты переходов.



                        S i (t )      x2 (t )         1
                                                     S j (t  1)
                                      x1 x2 (t )      2
                                                     S j (t  1)
     Для этого фрагмента ПТП x1i , j  xi2, j  1 . Полнота переходов может быть
обеспечена вводом запрещенного входного сигнала, для которого событие
перехода будет неопределенным.
                         xзапр.  x2  x1 x2  x1 x2
      Скорректированный фрагмент ПТП будет иметь вид:

                        S i (t )    x2 (t )           1
                                                     S j (t  1)
                                    x1 x 2 (t )        2
                                                     S j (t  1)
                                             
                                    ( x1 x2 ) (t )   S ( )
     Здесь знаком * будем обозначать запрещенный входной сигнал, а
знаком S () — неопределенное событие.
          Полный запрещенный входной сигнал для всех ветвей
алгоритма управления на определенном его шаге в алфавите [Х].
          Полный абстрактный запрещенный входной сигнал для всех
ветвей алгоритма управления на всех его шагах в алфавите [Z].


                                                                              22