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

      Из сформулированного утверждения и изложенного выше можно
вывести следующее следствие:
        Если в исчислении предикатов первого порядка некоторый предикат
P(t) можно эквивалентными преобразованиями в алфавите [Z] привести к
виду  A  , то предикат P(t) в этом же алфавите [Z] описывает вполне
определенное регулярное выражение алгебры событий и на основании первой
теоремы С.К.Клини [13] представим в конечном цифровом автомате.

     4.2.2. Формализация словесных алгоритмов, определяю-
щих реализуемые в цифровом автомате события, на основе
использования языка исчисления предикатов
       Для удобства и упорядочения формы записи исходных предикатных
формул, формализующих словесные алгоритмы, введем понятие номера и
ранга рассматриваемого события и номера ветви алгоритма, определяющей
это событие [12].
       Номером события S будем называть натуральное число 0,1,2,…,,…,
приписываемое к обозначению события в качестве первого нижнего индекса.
       Рангом события S  будем называть натуральным число 0,1,2,…,,…,
приписываемое к обозначению события в качестве второго нижнего индекса.
       Событием нулевого (старшего) ранга относительно описываемого
события S  будем называть самое это событие S  , а также события,
непосредственно определяющие событие S  как произвольную двузначную
функцию [36].
       Событием первого ранга относительно события S  будем называть
каждое событие, непосредственно предшествующее событию S  .
       Событием (+1)-го ранга относительно события S  будем называть
каждое событие, непосредственно предшествующее любому из событий -го
ранга относительно события S  .
       Если событие S, непосредственно определяется логической суммой
других событий, то для отличия таких дизъюнктивных членов введем первый
верхний индекс, который будем называть номером ветви алгоритма,
определяющего событие S  . При этом различные ветви алгоритма должны
иметь различные номера, т.е. обозначения событий, порожденных различным
образом из исходного, при одинаковых нижних индексах должны иметь
различные первые верхние индексы.
       Для формального описания на языке исчисления предикатов
словесных алгоритмов, определяющих реализуемые в цифровом автомате
события, можно воспользоваться результатами, получаемыми в разделе 4.2.1
относительно представления любого регулярного выражения алгебры


                                                                      81