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

регулярных выражений алгебры событий под входной буквой будем
понимать также частный входной сигнал, который равен конъюнкции
(комбинации) тех элементарных входных сигналов, которые действуют в
данный момент автоматного времени одновременно. Такую конъюнкцию
будем заключать в круглые скобки. Например, для события, записанного в
виде выражения:
                           W
                         S    S 0 ( x1 x2 )( x2 x3 x4 )( x4 )
элементарные конъюнкции ( x1x2 ) , ( x2 x3 x 4 ) , ( x4 ) - представляют собой
частные входные сигналы, действующие на входе автомата в
соответствующие такты его работы и могут быть обозначены одной буквой,
например:  i  x1 x2 ;  j  x1 x3 x4 ;  k  x 4 .
        Приведем         пример     составления     регулярного    выражения,
определяющего закон функционирования цифрового автомата.
        П р и м е р 4.1. Пусть необходимо описать автомат, выдающий
сигнал W k в течении одного такта всякий раз, когда происходит изменение
входной буквы с z1 на z2. Формулируя это условие по другому, можно
сказать, что сигнал Wk должен выдаваться в ответ на любые входные
последовательности, кончающиеся последовательностью z1z2. Фраза «любые
входные последовательности» формализуется так называемым всеобщим или
универсальным событием, состоящим из всех возможных слов в алфавите
Z  z1, z2  . Тогда событие, в ответ на которое должен выдаваться сигнал Wk,
на основании (4.2) и (4.4) будет описываться регулярным выражением
S Wk  z1  z2 z1 z2 .


  4.1.2. Построение СКУ по регулярному выражению алгебры
                 событий и ее детерминизация
      Предлагаемый способ построения СКУ по регулярному выражению
алгебры событий основывается на следующих предложениях [32,33]. Любое
регулярное выражение алгебры событий, представляющее в цифровом
автомате событие S Wα β , в общем случае может быть записано в виде
                                             k
                                 S Wα β    V S iα ,                 (4.10)
                                            i 1


где  - номер события;
    k – число параллельных ветвей алгоритма, определяющих событие S α
        (число дизъюнктивных членов регулярного выражения);
      i
    S α - обозначение события, описывающего i – ю ветвь алгоритма.



                                                                              67