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

      Событие S iα , в свою очередь, может быть сведено к произведению
элементарных одноэлементных событий. Действительно, если произвести
замену итерации в описании события S iα там, где она есть, то получим

                               S i  S 0 z   z p  z r z                        (4.11)
                                                   
                                                     n букв


      Исходя из интерпретации регулярного выражения алгебры событий,
выражение (4.11) может быть представлено в виде следующей системы
регулярных выражений:
                                       S i ,0  Si ,1 z  ,

                                       S i ,1  S i ,2 z r ,
                                       
                                                                                    (4.12)
                                       S i ,      S i ,1 z p   ,
                                       
                                       S i ,n1  S 0 z
где  - порядковый номер буквы zp, начиная с конца выражения (4.11) (
       называется рангом события и используется в качестве второго
       нижнего индекса);
   S 0 - обозначение начального события, равного {е}; поскольку {е}=е и
       еP=Pе=P (закон нейтральности пустого слова), то событие S 0 может
       быть всегда добавлено в регулярное выражение;
   S i ,1 -   обозначение     события,              непосредственно      предшествующего
                   i
         событию S ,;

   n – число входных букв в выражении (4.11).
      Если в выражении (4.11) была произведена замена вида
                                z p  R,
где R – произвольное регулярное выражение, то используя тождество (4.1),
получим
                          S i ,  S i ,1 R  S i ,1  S i , R           (4.13)
Применяя рассмотренные операции к выражению (4.13), можно также свести
его к выражениям типа (4.10), (4.11) и (4.12).
       Исходя из изложенного, алгоритм построения СКУ по заданным
регулярным выражениям исходной системы событий будет содержать
следующие этапы:


                                                                                             68