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

(или событиям). Причем эти переходы для каждого входного сигнала
являются однозначными.
      б)     Недетерминированная        СКУ      представляется    системой
«рекуррентных» формул. Это означает, что каждое событие Sj из множества
реализуемых в автомате событий, может быть определено через событие Si
(события), имеющее место в предшествующий момент автоматного времени.
При этом в начале работы автомата может быть истинным то событие
(события), для которого в предшествующий момент времени было истинным
событие S0.
      в) В названии системы НД СКУ присутствует слово «каноническая».
Этим названием подчеркивается тот факт, что все переменные в правой части
уравнений НД СКУ взяты для одного и того же момента времени (t).
      г) Учитывая, что правая часть формул НД СКУ представляет собой
ДНФ булевых функций от двух типов переменных, представляющих как
входные сигналы, так и события, то к этим формулам могут быть применены
все законы и методы преобразования булевых функций.
      д) Учитывая также, что для систем (1.1) и (1.12) можно было бы вместо
знака равенства поставить знак         , являющийся знаком сокращенного
обозначения, означающим, что предикат, стоящий слева от этого знака,
является сокращенным обозначением предикатной формулы, расположенной
от него справа [15, стр. 222, 226], то возможно применять к формулам НД
СКУ все законы и методы преобразования, принятые в исчислении
высказывания и предикатов.
      е) Исходя из изложенного, целесообразно математическую модель
НДА, представленную на языке НД СКУ, называть в дальнейшем
автоматной моделью НДА, хотя во многих работах по теории цифровых
автоматов слово «автоматность» всегда отождествлялось с понятием
детерминированного автомата. При введении такого названия автор исходил
из того, что в названии математической модели автомата словом
«автоматная» в первую очередь подчеркивается задание функций
переходов в автомате в явном виде.
      ж) В связи с тем, что НДА является обобщением конечного
детерминированного        автомата,      то     математическую       модель
детерминированного автомата (ДА), представленную на языке СКУ, будем
называть автоматной моделью ДА. Для такого автомата СКУ будет
представлять собой функции переходов в автомате, когда переход в любое
состояние интерпретируется как событие.
      В заключение отметим, что в ряде работ автора приведены алгоритмы
синтеза автоматных моделей управляющих автоматов, заданных на
некоторых начальных языках: операторных схем алгоритмов (ОСА), в том
числе с параллельными ветвями (ОСАП) [2, 16—19], на языке регулярных
выражений алгебры событий [2, 20], на языке исчисления предикатов 1-го
порядка [9].


                                                                         20