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

            1) В каждом из регулярных выражений исходной системы событий
S1 , S 2 ,..., S  ,..., S M , отмеченными соответствующими выходными сигналами,
                                                           
выделяют параллельные ветви, описывающие события S    1, M .     
                                                    
      2) Для каждой параллельной ветви S i i  1, k каждого из регулярных
выражений исходной системы событий выполняют операцию замены
итерационных скобок (внешних) там, где они имеются, одной из
вспомогательных переменных, которые будут играть роль дополнительных
                             
входных букв. Например, Ri , p  zi , p , где Ri , p - регулярное выражение,
входящее в итерационные скобки i –ой ветви события S  , р – порядковый
номер итерационных скобок в i –ой ветви.
      3) Каждое событие S i преобразуют в систему рекуррентных
регулярных соотношений вида (4.12).
       4) Выполняют подстановку вместо буквы типа z i , p соответствующие
                        
итерационные скобки Ri , p и осуществляют их раскрытие в соответствии с
тождеством (4.1).
       5) Если содержимое итерационных скобок какого-либо частного
события из полученной системы соотношений вида (4.12) включает более
одной буквы, в т.ч. и итерационные скобки (внутренние), то для этого
события повторяют все операции, предусмотренные п.п. 1-5 и т.д. до тех пор,
пока не будут раскрыты все итерационные скобки в регулярных выражениях
всех событий, входящих в исходную систему.
       Примечание: Для уменьшения числа итерационных скобок целесообразно
использовать дополнительные тождественные соотношения алгебры событий.
       6)   Выполняют для      каждого    события     S   исходной системы
подстановку вместо обозначения событий S i соответствующих им
выражений.
        Аналогичную подстановку делают и в том случае, если в процессе
преобразований описания некоторых частных событий будут содержать
обозначения непосредственно предшествующих событий без входных букв.
В этом случае необходимо сделать подстановку вместо обозначения таких
событий соответствующих им выражений.
        7) Во всех описаниях, полученных частных событий, заменяют знаки
конкатенации на знаки конъюнкции и, вводя дискретное время, как принято в
(2.3), получают искомую СКУ, в которой обозначения событий исходной
системы отмечаются соответствующими выходными сигналами.
        Примечание: Принятый способ нумерации событий и букв удобен при
выполнении всех приведенных выкладок и не является обязательным. При небольшом
числе событий может оказаться более удобным нумеровать события с использованием
одного индекса.



                                                                              69