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

это будет свидетельствовать о правильности системы уравнений для Q-
событий, построенной по результатам кодирования исходной СКУ.
Для выполнения операции детерминизации СКУ для Q-событий с целью ее
контроля необходимо алгоритм детерминизации, рассмотренный в главе 2,
дополнить пунктами, вытекающими из специфики формирования полных
событий (состояний автомата) и возможности отсутствия полноты входных
сигналов, вызывающих переходы в Q-события. Это связано с тем, что полные
события при их кодировании представляются в виде конъюнкции
переменных Q , часть из которых может быть взята с отрицанием.
Таким образом, в алгоритм детерминизации необходимо ввести следующие
дополнения и разъяснения:
1) Если исходная система уравнений для Q-событий состоит из R уравнений,
то любое полное cобытие, которое получается в результате детерминизации
такой системы должно быть представлено конъюнкцией (сочетанием) из R
       ~    ~   ~
букв: Q1  Q QR , некоторые из которых могут быть как с отрицанием, так
и без отрицания. Откуда следует, что, если на очередном шаге алгоритма
детерминизации будут выводимы только некоторые из R событий, то
сочетание этих событий необходимо дополнить отрицаниями тех Q-событий,
которые не вошли в полученное сочетание.
В том случае, если на каком-то шаге алгоритма детерминизации не будет
выводимо ни одно из Q-событий, то получим полное событие, равное
конъюнкции отрицаний из всех Q-событий. Такое событие, ранее было
названо пустым событием. В нашем случае это полное событие может быть и
не пустым, ему соответствует код Q1 QR , принятый при кодировании
некоторого полного события.
2) Начало работы алгоритма детерминизации определяется начальным
полным событием, поэтому его код должен быть зафиксирован в первой
строке (первый шаг алгоритма детерминизации) прямой таблицы переходов
детерминизации СКУ для Q-событий.
3) Если при определении сочетаний частных входных сигналов на переходе
Х(am,aS) их совокупность на каком-либо шаге алгоритма детерминизации не
удовлетворяет условиям полноты, то эта совокупность входных сигналов
должна быть дополнена в соответствии с рекомендациями пункта 3
алгоритма детерминизации (глава 2). При этом необходимо иметь в виду, что
для дополненных входных сигналов события переходов и соответствующие
им состояния переходов (полные события) не будут неопределенными, так
как выполняемая операция над СКУ для Q-событий относится к реальному,
вполне определенному автомату.
П р и м е р 5.2. Выполнить операцию детерминизации системы уравнений
для Q-событий (5.16), полученной в результате кодирования СКУ (3.11).
В соответствии с системой уравнений (5.16) построим вспомогательную
прямую таблицу переходов для Q-событий (табл.5.2).

                                                                        145