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

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

65
8.
P
P
P
P
}
{
}
{
- закон коммутативности для
итерации;
9.
}
{
}
{
}
{
P
P
P
- закон мультипликативного
поглощения для итерации;
10.
}
{
}
{
P
P
P
- закон дизъюнктивного
поглощения для итерации;
11.
S
S
S
e
e
- закон нейтральности пустого
слова;
12.
e
e
}
{
.
В этих соотношениях P, Q, S – обозначают произвольные события, а
е
– событие, состоящее из одного пустого слова.
Приведем некоторые дополнительные тождественные соотношения
алгебры событий, полученные в [30]:
1.
}
{
}}
{
}
{{
Q
P
Q
P
;
2.
}
{
}}
}{
{
{
S
Q
P
S
Q
P
;
3.
}{,}{ QPQPZQP
;
где
QPZ ,
- регулярное выражение, построенное из P и Q с помощью трех
основных операций алгебры событий;
4.
}
{
}}
{
{
Q
P
Q
P
;
5.
}{},{ QPQPZQP
;
6.
}{},}{{ QPQPZQP
.
Можно доказать следующее важное соотношение, позволяющее
раскрывать итерационные скобки:
если
}
{
Q
S
P
, то
PQ
S
P
. (4.1)
Действительно, используя тождество
}
{
}
{
Q
Q
Q
e
и закон
нейтральности пустого слова, получим
}{}{}{ QSQSQSQSQQSP
e
e
.
Применяя правило
Q
Q
Q
Q
}
{
}
{
, будем иметь:
Q
Q
S
S
P
}
{
, где
заменяя
P
Q
S
}
{
, получим искомое соотношение (4.1). С другой стороны,
если
Q
e
, то уравнение
S
QP
P
имеет решение
S
Q
P
}
{
.
Здесь уместно еще раз обратить внимание на фундаментальное
значение для теории конечных цифровых автоматов известных теорем
С.К.Клини [13, 15], в которых было впервые доказано, что класс событий,
представимых в конечных цифровых автоматах, совпадает с классом
регулярных событий. Это означает, что: 
      8. P {P}  {P} P                     - закон коммутативности для
                                              итерации;
      9. {P}{P}  {P}                      - закон мультипликативного
                                              поглощения для итерации;
      10. {P} P  {P}                     - закон дизъюнктивного
                                              поглощения для итерации;
      11. eS  Se  S                      - закон нейтральности пустого
                                              слова;
      12. {e}  e .
      В этих соотношениях P, Q, S – обозначают произвольные события, а е
– событие, состоящее из одного пустого слова.
      Приведем некоторые дополнительные тождественные соотношения
алгебры событий, полученные в [30]:
      1. {{P}{Q}}  {P  Q} ;
      2. {P  {Q}{S }}  {P  Q  S} ;
      3. {P  Q}  Z P, Q   {P  Q} ;
где Z  P, Q  - регулярное выражение, построенное из P и Q с помощью трех
                  основных операций алгебры событий;
        4. {P  {Q}}  {P  Q} ;
      5. {P  Q  Z P, Q }  {P  Q} ;
      6. {P  Q}{Z  P, Q }  {P  Q} .
      Можно доказать следующее важное соотношение, позволяющее
раскрывать итерационные скобки:
      если P  S{Q} , то P  S  PQ .              (4.1)
      Действительно, используя тождество {Q}  e  Q{Q}              и     закон
нейтральности пустого слова, получим
                P  S e  Q{Q}  Se  SQ{Q}  S  SQ{Q} .
       Применяя правило Q{Q}  {Q}Q , будем иметь: P  S  S{Q}Q , где
заменяя S{Q}  P , получим искомое соотношение (4.1). С другой стороны,
если e  Q , то уравнение P  QP  S имеет решение P  {Q}S .
      Здесь уместно еще раз обратить внимание на фундаментальное
значение для теории конечных цифровых автоматов известных теорем
С.К.Клини [13, 15], в которых было впервые доказано, что класс событий,
представимых в конечных цифровых автоматах, совпадает с классом
регулярных событий. Это означает, что:



                                                                              65

Страницы