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

   Глава 4. Начальные языки, используемые для
     представления управляющих алгоритмов
      параллельной обработки информации

       В качестве начальных языков для формального представления
параллельных алгоритмических процессов и их отдельных ветвей в данной
работе рассматриваются:
          язык регулярных выражений алгебры событий (РВАС);
          язык исчисления предикатов первого порядка с ограниченными
кванторами и его связь с языком РВАС;
          язык операторных схем алгоритмов с параллельными ветвями
(ОСАП), базирующийся на его графическую интерпретацию – язык граф-
схем алгоритмов с параллельными ветвями (ГСАП). Кроме того,
рассматриваются и обычные непараллельные языки – язык граф-схем
алгоритмов (ГСА) и язык логических схем алгоритмов (ЛСА), т.к. они
являются основой для построения параллельных языков ОСАП.
       Для каждого начального языка, кроме основных понятий и
определений, рассматривается методика их использования для представления
алгоритмических процессов и методика преобразования описания
алгоритмических процессов на начальном языке к описанию на стандартном
языке в виде системы канонических уравнений для всех событий,
реализуемых в алгоритме управления преобразованием информации.

   4.1.Язык регулярных выражений алгебры событий
          4.1.1.Основные понятия и определения языка РВАС
      Язык регулярных выражений алгебры событий (РВАС) нашел
применение при построении различных управляющих и операционных
устройств, например, для построения синтаксических анализаторов и
устройств преобразования цифровой информации, для описания протоколов
в компьютерных сетях и др.
       Язык РВАС базируется на использовании алгебры событий, что
позволило представлять бесконечные события, реализуемые в устройствах
преобразования информации, конечными выражениями. В данном случае под
преобразованием информации понимается процесс отображения множества
слов в некотором конечном входном алфавите в множество слов в конечном
выходном алфавите. Особенно удобен язык РВАС для решения задач
распознавания цепочек слов и их принадлежности к тому или иному языку.
       В связи с тем, что в соответствии с известными теоремами С.К.Клини
[15] в конечном цифровом автомате представимы только регулярные

                                                                       62