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

события, то язык РВАС имеет исключительно важное значение в теории и
практике разработки способов описания законов функционирования
цифровых автоматов на других начальных языках, когда решаются вопросы о
представлении таких описаний в цифровых автоматах.
      Язык РВАС и его использование для синтеза цифровых автоматов был
впервые фундаментально представлен в монографии академика
В.М.Глушкова «Синтез цифровых автоматов» [1]. Следуя [1], введем
некоторые понятия и определения из теории языка РВАС.
      Событием в любом конечном входном алфавите [Z] называют
произвольное множество слов в этом алфавите.
       Событие S αWβ , имеющее номер , будет представленным буквой W  в
любом заданном отображении  с алфавитами [Z] и [W], если для каждого
входного слова p(t) этого события из алфавита [Z] соответствующее ему
выходное слово q(t) будет оканчиваться буквой W  , входящей в алфавит [W],
т.е. имеем q(t)=[ p(t)]. Такому определению события не противоречит
определение события, данное в главе 2 данного пособия.
       Элементарными событиями в алфавите Z  z1 , z 2 ,..., z F  называются
события, состоящие из одной буквы алфавита [Z] и событие S=е, где е –
пустое слово.
       Множество всех событий, каждое из которых отмечено одним из
выходных сигналов алфавита [W] называют каноническим множеством
событий, соответствующих отображению .
       Для всякого автоматного отображения  определяемое им множество
событий должно удовлетворять условиям автоматности, которые
формулируются таким образом:
       1) События, входящие в автоматное множество событий, попарно не
пересекаются и не содержат пустого слова (условие однозначности).
       2) Начальные отрезки слов, принадлежащие какому-нибудь событию
из автоматного множества событий, за исключением пустого слова,
принадлежат каким-либо событиям из того же самого множества (условие
полноты).
       Под алгеброй событий в алфавите [Z] понимается множество всех
событий в этом алфавите, на котором определены две двухместные операции
– дизъюнкция и умножение и одна одноместная операция, называемая
итерацией.
       Дизъюнкция двух событий S1  S 2 - это теоретико-множественное
объединение этих событий.
       Произведение (или конкатенация) двух событий S 1 S 2 - это событие,
состоящее из всех слов вида k 1 k 2 , где k1 - любое слово из S 1 , а k 2 - любое
слово события S 2 . При этом S 1 S 2  S 2 S 1 , т.е. эта операция отличается от
операции логического умножения. В дальнейшем, если такая операция
                                                                               63