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

       1) Событие, представленное в произвольном конечном автомате Мили
или Мура некоторым множеством выходных сигналов или состояний,
обязательно регулярно.
       2) Любое регулярное событие может быть представлено в конечном
автомате Мили или Мура некоторым множеством выходных сигналов или
состояний.
           Приведем примеры регулярных выражений для входного алфавита
[ Z ]  [ z1 , z 2 ,..., z F ] некоторых характерных событий, которые могут быть
полезными для описания законов функционирования автоматов [31]:
           1. Всеобщее или универсальное событие – это событие, состоящее из
всех возможных слов входного алфавита [Z]:
                                  I  z1  z2    z F                 (4.2)
            2. Событие, включающее все возможные слова, состоящие из букв
zi ,..., z j :
                      S  {zi  ...  z j } , где zi ,..., z j  Z          (4.3)
     3. Событие, содержащее все слова, оканчивающиеся отрезком р.
Например, для p  zi z j имеем:
              S  { z1  z 2  ...  zi  z j  ...  z F }zi z j  Izi z j     (4.4)
       4. Событие, содержащее все слова, в которых хотя бы один раз
встречается отрезок слова р в любом месте. Например, для p  zi z j имеем:
                                 S  IpI  Izi z j                              (4.5)
       5. Событие, состоящее из всех слов, имеющих начальные и конечные
отрезки p1 и p 2 соответственно. Например, для p1  zi , p2  z j z k имеем:
                              S  p1Ip2  zi Iz j zk                            (4.6)
       6. Событие, содержащее все слова длины r :
        S  S1S2 ...S j ...Sr , где S j  z1  z2  ...  z F , j  1, r        (4.7)
       7. Событие, содержащее все слова длиной, кратной r :
        S  {S1S 2 ...S j ...S r } , где S j  z1  z2  ...  z F , j  1, r   (4.8)
      8. Событие, состоящее из всех слов алфавита Z  z1, z2  , не
содержащих серии из r букв z1 и оканчивающихся буквой z2 :
                                                                   
                                                                   
              S   z 2  z1 z 2  z1 z1 z 2  ...  z1 z1  z1 z 2   (4.9)
                                                            
                                                    ( r 1) букв  
       Как было отмечено выше (гл.1), для многих практических реальных
автоматов в качестве входного (выходного) алфавитов целесообразно
использовать множество элементарных входных (выходных) сигналов. В
этом случае при формализации закона функционирования автомата на языке
                                                                                        66