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

      Начальные языки характеризуются тем, что функции переходов
автоматов в описании их закона функционирования на этих языках
представлены не в явном виде. К числу таких языков относятся, например,
такие известные языки, как язык регулярных выражений алгебры событий
(РВАС), язык логики одноместных предикатов, языки операторных схем
алгоритмов (ОСА), языки операторных схем алгоритмов с параллельными
ветвями (ОСАП) и др.
      Стандартные языки, в отличие от начальных, характеризуются тем,
что в описании закона функционирования автоматов на этих языках,
функции переходов представлены в явном виде. К числу таких языков
относятся: различные типы таблиц переходов и выходов, матрицы переходов,
направленные графы и системы канонических уравнений.
      Стандартный язык, представляя функции переходов автомата в явном
виде, позволяет непосредственно перейти к структурной реализации
управляющего устройства (автомата). С другой стороны, на стандартном
языке в большинстве случаев затруднительно выполнять «перевод»
неформального словесного описания алгоритма функционирования автомата
на формальное описание, т.е. говорят, что стандартный язык обладает
небольшими выразительными возможностями.
      В связи с этим для первоначального описания алгоритма логического
управления по его словесному неформальному описанию, представленному в
техническом задании, целесообразно использовать начальные языки, к
которым предъявляются следующие основные требования [8, 13, 14]:
       Язык должен обладать достаточно широкими выразительными
возможностями и быть удобным не только для перевода на этот язык часто
встречающихся словесных описаний алгоритма управления, но и должен
быть достаточно удобным переход от начального формального описания к
каноническим уравнениям стандартного языка. Кроме того, язык должен
также содержать необходимые средства и методы для эквивалентных
преобразований и выполнения контрольных процедур описания на
начальном языке.
       Описание алгоритма управления, полученное на основе
использования начального языка и представленное в виде системы
уравнений, формализующих все реализуемые в алгоритме события, должно
быть выражено в виде регулярных формул. Это требование следует из
известной теоремы С.К.Клини [15], в которой утверждается, что для того
чтобы события были представлены в конечном автомате, необходимо и
достаточно, чтобы они были регулярными, т.е. описание таких событий
должны быть получены из описания элементарных событий с
использованием только трех операций алгебры событий: дизъюнкции,
конкатенации и итерации. Таким образом, когда задание на реализацию
алгоритма управления будет выражено на языке регулярных формул, то
говорят, что проблема распознавания и синтеза управляющего устройства в
соответствии с заданным алгоритмом не возникает [13].
                                                                      11