Теория алгоритмов и формальных языков. Мелихов А.Н - 69 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

Легко видеть, что если исходные события конечны, то в результате дизъюнкции и
умножения получаем события, состоящие из конечного множества слов. Применение
итерации приводит к появлению событий, состоящих из бесконечного множества слов.
Пусть
{}
21
, xxV
x
= и заданы события
{
}
121
,, xxxP
=
и
{
}
2122
,,, xxxxR
=
в алфавите
x
V . На основании определений операций можно построить события
{}
*
,, PRPPvR ⋅ ,
имеющие вид:
{}
{}
{}
},,,
,,,,,,,,,,{
,,,,,,,,,,,,
,,,,,,,
12121121111212
1112112111112121121121211112
*
21122212211221
2122121
Kxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxP
xxxxxxxxxxxxxxRP
xxxxxxxPvR
λ
=
=⋅
=
Заметим, что одноэлементные события
λ
, образованные пустым словом
λ
,
состоит из одного слова нулевой длины. Условимся не считать события различными ,
отличающиеся друг от друга только пустыми словами
λ
. Кроме события
λ
будем также
рассматривать пустое событие Ø, которое состоит из пустого множества букв входного
алфавита и поэтому является частью любого события.
Пусть
{}
mx
xxxV ,,,
21
K= - произвольный алфавит. Введем теперь понятие
регулярного выражения в алфавите
x
V , которое определяется следующим образом:
1)
символы
m
xxx ,,,
21
K и Ø являются регулярными выражениями;
2)
если
P
и
R
- регулярные выражения, то таковыми являются
{}
*
,, PRPPvR ⋅ и
{
}
*
R ;
3)
никакое другое выражение не является регулярным, если оно не получено путем
конечного числа применений правил 1) и 2).
Таким образом регулярное отношение – формула в алгебре событий, причем одно и то
же событие может быть по разному выражено через одноэлементные события и операции
{}
*
,,⋅v . Те события, для которых существует регулярные выражения, называются
регулярными событиями. В противном случае событие называется нерегулярным.
Законы эквивалентности преобразования регулярных выражений играют важную
роль в алгебре событий. Пусть TRP ,,- регулярные события из
*
x
V . Тогда справедливы
следующие соотношения:
Pv Ø=Ø PvP = ;
⋅
P
Ø=Ø =⋅
P
Ø;
{Ø}
*
=
λ
;
{
λ
}
*
=
λ
;
;RvPPvR =
{} {}
;
**
PPPP ⋅=⋅ коммутативность v и
{
}
*
vTPvRRvTPv )()( =
TRPTRP ⋅
⋅
=⋅⋅ )()(
ассоциативность
v и
)()()( TPvRPRvTP ⋅
⋅
=⋅
)()()( TRvTPTPvR ⋅⋅=
левая и правая дистрибутивность относительно
v
{} {}
**
PvPP ⋅=
λ
- развертывание итерации

Страницы