Page 22 - 4625

{P} = {}  P  P*P  ……. (операція ітерації).
П5. Ніякі інші множини, окрім побудованих на основі
ПП 1-4, не є регулярними множинами.
Таким чином, регулярні множини можна побудувати
з базових елементів ПП 1-3 шляхом скінченного
застосування операцій об’єднання, конкатенації та ітерації.
Регулярні вирази позначають регулярні множини таким
чином, що:
П1. 0 – позначає регулярну множину ;
П2.  – позначає регулярну множину {};
П3. а – позначає регулярну множину {a};
П4. якщо p та q позначають відповідно регулярні
множини P та Q, то:
p + q позначає регулярну множину P  Q;
p - p позначає регулярну множину P*Q;
p* позначає регулярну множину {P}.
П5. Ніякі інші вирази, окрім побудованих на основі
ПП 1-4 не є регулярними виразами.
Оскільки ми почали вести мову про вирази, нам
зручніше перейти до поняття алгебри регулярних виразів.
Для кожної алгебри одним з важливих питань є питання
тотожних перетворень, які виконуються на основі
тотожностей у цій алгебрі. Сформулюємо основні тотожності
алгебри регулярних виразів:
1) a + b = b + a;
2) a = a = a;
3) a0 = 0a = 0;
4) a(b + c) = ab + ac;
5) (a + b)c = ac + bc;
6) a + a = a;
7) a + b + c = a + (b + c);
8) a + b + c = (a + b ) + c;
9) p + p* = p*;
10) 0* = ;
11) * = .
21