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

встречается в каком-либо выражении одновременно с операцией логического
умножения, то последнюю операцию будем обозначать символом &.
            Итерация события S, записываемая в виде {S} – это событие,
состоящее из пустого слова е и всевозможных слов вида p1 p 2 ... pn , где
 p1 , p 2 , ..., p n - произвольные слова события S, а n – любое натуральное число
n = 1, 2, …
       {S}= еS SS SSS  … .
       В алгебре событий при отсутствии в выражении обычных скобок,
изменяющих обычный порядок действий, сначала должны выполняться
итерации, затем конкатенация и потом дизъюнкция.
       Регулярное событие – это событие, которое можно получить из
элементарных событий в результате применения конечного числа раз трех
основных операций алгебры событий. Необходимо иметь в виду, что не все
события являются регулярными. Например, не являются регулярным
событием множество всех последовательностей z1 z1  z1 z 2 , таких что их
длина выражается простым числом [44].
       К числу не основных операций в алгебре событий относят операцию
дополнения события и двуместную операцию пересечения событий.
      Дополнением S события S в некотором алфавите [Z] называется
множество всех слов в алфавите [Z], которые не вошли в событие S .
       Пересечением S 1 & S 2 событий S1 и S 2 называется событие,
состоящее из всех слов, входящих одновременно в оба события S1 и S 2 .
      Регулярное выражение алгебры событий – это всякое представление
регулярного события через элементарные события и указанные операции
алгебры событий, включая и не основные операции.
      Так как одно и тоже регулярное выражение допускает много
различных представлений, то в ряде случаев может возникнуть проблема
эквивалентных      преобразований      регулярных    выражений.       Такие
преобразования могут быть выполнены с помощью следующих
тождественных соотношений [1]:
      1. P  Q  Q  P                  - коммутативность дизъюнкции;
       2. P  (Q  S )  ( P  Q)  S      - ассоциативность дизъюнкции;
       3. P  P  P  ...  P  P          - идемпотентность дизъюнкции;
       4. P (Q S )  ( P Q ) S             - ассоциативность умножения;
      5. P (Q  S )  PQ  PS             - левая и правая дистрибутивность
         ( P  Q ) S  PS  Q S             умножения по отношению к
                                            дизъюнкции;
       6. {{P}}  {P}                      - идемпотентность итерации;
       7. {P}  e  P{P}                  - правило развертывания итерации;

                                                                                64