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

      П р и м е р 4.2. Рассмотрим без дополнительных пояснений пример
построения СКУ по следующему регулярному выражению:
           S W  S 0 z 2 z1  z 2 z 2 z1  S 0 z1 z 2   S W,1  S W,2 ,

           S W,1  S 0 z 2 z1  z 2 z 2 z1  S 3 z1 ,
           S 3  S 0 z 2 z1  z 2 z 2  S 4 z 2 ,
           S 4  S 0 z 2 z1  z 2   S 0 z 2  S 4  z1  z 2 ,
           S W, 2  S 0 z1 z 2 z 2  S 5 z 2 ,
           S 5  S 0 z1 z 2   S 0  S 5 z1 z 2  S 0  S 6 z 2 , S 0  S 5 ,
           S 6  S 5 z1 ,
где  - знак выводимости.
      Окончательно СКУ будет иметь вид:
           SW t  1  S3 t  & z1 t   S5 t  & z2 t ,
           S3 t  1  S4 t  & z2 t ,
           S4 t  1  S0 t  & z2 t   S4 t  & z1 t   z2 t ,        (4.14)
           S5 t  1  S 0 t   S6 t  & z2 t ,
           S 6 t  1  S5 t  & z1 t .
       В общем случае СКУ, полученная по регулярным выражениям
алгебры событий недетерминирована. Это относится не только к СКУ,
полученной по системе регулярных выражений с общими начальными
событиями, но и к СКУ, полученной по одному регулярному выражению,
включающему только одну ветвь с итерационной скобкой. В связи с этим для
таких СКУ в целях дальнейшего синтеза автомата может потребоваться их
детерминизация.
       Если в качестве входных сигналов в исходных регулярных
выражениях алгебры событий используются частные входные сигналы из
структурного алфавита, то детерминизацию СКУ необходимо проводить в
соответствии с алгоритмом, предложенным в гл.2.
       Если в качестве входных сигналов в исходных регулярных
выражениях алгебры событий используются, как обычно принято, полные
входные сигналы из абстрактного алфавита [Z], то алгоритм детерминизации
упрощается, т.к. на входе автомата в любой момент автоматного времени
может появиться только одна из букв входного алфавита [Z], но не их
сочетание.
       В связи с отмеченными замечаниями при построении прямой таблицы
переходов детерминированного автомата для каждой строки таблицы в
столбце 3 выписываются все входные сигналы из абстрактного алфавита [Z],
а для обычной таблицы переходов детерминированного автомата каждая

                                                                                           70