Нехай P1, P2 X* – події в алфавіті X. Розглянемо три операції над подіями, які називатимемо регулярними операціями.
1.Об'єднання (іноді диз'юнкція) подій P1 P2 – це звичайне теоретико-множинне об'єднання.
2.Множення (конкатенація) подій P1P2 – це подія, яка скла-
дається зі всіх таких слів w1w2, що w1 P1 і w2 P2. Зазвичай операцію множення подій використовують без спеціального позначення. Для зручності посилання на цю операцію позначатимемо
їїчерез .
3.Ітерацією події P називають подію
P* = {e} P P2 ... Pn ... = ∞ Pn .
n=0
Тут через P0 позначено подію {e}, а через Pn – подію PP…P (n разів). Іноді операцію ітерації події P позначають {P}.
Звернемо увагу на те, що введене вище позначення X* для множини всіх слів у алфавіті
X= {x1, x2, …, xm}
іпозначення X* операції ітерації для події X мають той самий
смисл. Дійсно, подія
X* = ({x1} {x2} … {xm})*
складається зі всіх слів (включаючи порожнє слово) в алфавіті X. Через P + позначатимемо подію P*\{e}.
Окремо зазначимо деякі важливі події. Подію, яка містить усі слова в алфавіті X, тобто X*, назвемо загальною. Подію, яка не містить жодного слова, назвемо порожньою, або неможливою й позначимо символом порожньої множини .
Використовуючи регулярні операції, круглі дужки та події в алфавіті X як операнди, одержуватимемо вирази, що задають певні події в алфавіті X. Щоб зменшити кількість дужок у виразах, домовимося про такі пріоритети для регулярних операцій: спочатку виконується ітерація, відтак – множення і, нарешті, – об'єднання.
Приклад 5.4.
1. Виписати всі слова події P* в алфавіті X = {a, b}, довжина
яких дорівнює k. |
|
(а) P = {ab, bb}, k = 6. |
(б) P = {aa, b}, k = 5. |
|
216 |
(а) ababab, ababbb, abbbab, abbbbb, bbabab, bbabbb, bbbbab, bbbbbb.
(б) aaaab, aabaa, baaaa, aabbb, baabb, bbaab, bbbaa, bbbbb.
2. Визначити, чи належать події P слова v і w. (а) P = {000}*{1}*{0}, v = 00011110, w = 11100.
(б) P = {001, 11}*{0, 11}, v = 11001110, w = 1001011.
(а) Слово v належить події P, тому що для його підслів маємо
000 {000}*, 1111 {1}* і 0 {0}. Слово w не належить події P,
оскільки слова події P, що містять принаймні один символ 1, закінчуються тільки одним символом 0.
(б) v P, w P. ◄
Вирази називають рівносильними (еквівалентними), якщо вони задають ту саму подію. Рівносильність виразів позначатимемо за допомогою знака =. Безпосередньо із означень випливають такі властивості регулярних операцій.
Нехай P, Q і T – довільні події. Тоді:
1)(P Q) T = P (Q T), (PQ)T = P(QT) – асоціативність;
2)P Q = Q P (комутативність об'єднання);
3)P(Q T) = PQ PT, (P Q)T = PT QT – дистрибутивність;
4)P P = P – ідемпотентність об'єднання;
5)(P*)* = P*, P*P* = P* – ідемпотентність ітерації;
6) |
PP* = P*P; |
|
|
7) |
P* = {e} |
PP* = ({e} P)*, {e}P = P{e} = P, {e}* = {e(5.6) |
|
|
} – |
||
властивостіподії {e});
8) P = P = , P = P, * = {e} – властивості порожньої події ;
9)(P Q)* = (P* Q*)* = (P*Q*)*;
10)(P* Q)* = (P Q)*;
11)P* = ({e} P P 2 … Pn – 1)(Pn)*.
Зазначимо, що операція множення подій некомутативна. Події {xi}, де xi X, називають елементарними. До елемен-
тарних подій належить також подія {e}.
Подія P називається регулярною, якщо вона є результатом застосування скінченної кількості операцій об'єднання, множення та ітерації до елементарних подій.
Точніше індуктивне означення регулярних подій таке:
1) елементарні події {e} та {xi}, xi X, i = 1, 2, …, m – регулярні;
217
2)якщо P1 і P2 – регулярні події, то P1 P2, P1P2 та P1* – регулярні події;
3)інших регулярних подій, окрім побудованих за правилами
1)і 2), немає.
Із означення випливає, що кожну регулярну подію можна зобразити (задати) деяким виразом (формулою), що складається зі скінченної кількості регулярних подій (операндів) і знаків регулярних операцій. Такі вирази називають регулярними. Регулярним виразом для порожньої події вважатимемо символ .
Регулярні вирази рівносильні (еквівалентні), якщо вони задають ту саму регулярну подію.
Усі наведені вище рівносильні співвідношення (5.6) справедливі й для регулярних подій, тобто мають місце також для довільних регулярних виразів. Як завжди в алгебрах, ці рівносильності дають змогу виконувати рівносильні перетворення (зокрема оптимізацію, або спрощення) регулярних виразів.
Очевидно, що будь-яка подія
{xi1xi2…xik},
що складається з одного слова в алфавіті X*, регулярна, оскільки вираз
{xi1}{xi2}…{xik},
що зображує цю подію, регулярний. Більш того, будь-яка скінченна подія
P= {w1, w2, …, wt}
єрегулярною та її можна задати виразом
{w1} {w2} … {wt}.
Регулярною є також загальна подія X*, оскільки
X* = ({x1} {x2} … {xm})*.
Зауважимо, що для зручності та компактності запису регулярних виразів часто випускають фігурні дужки в позначеннях елементарних подій і замість подій (множин) {xi} записують просто
xi, i = 1, 2, …, m,
а замість {e} – e. Іноді для більшої коректності замість {xi} пи-
шуть xi або xi.
Має місце така центральна теорема теорії автоматів (Кліні): подія P зображувана в скінченному автоматі тоді й тільки тоді,
218
коли вона регулярна. Теорема Кліні визначає ту центральну роль, яку відіграють регулярні події й відповідні регулярні вирази в теорії автоматів.
Приклад 5.5.
1.Написати регулярний вираз у алфавіті X = {0, 1}, який задає подію, що складається зі всіх слів таких і тільки таких,
(а) у яких кількість символів 0 кратна трьом; (б) які містять рівно три символи 1; (в) що містять 01011 як підслово.
(а) {1*01*01*01*}*; (б) 0*10*10*10*; (в) {0, 1}*01011{0, 1}*.
2.Написати регулярний вираз у алфавіті X = {0, 1, 2}, який задає подію, що складається зі всіх слів таких і тільки таких, у
яких п'ятим символом з кінця є 2. {0, 1, 2}*2{0, 1, 2}4.
3.Описати звичайними словами мову (подію) P у алфавіті X = {a, b}, задану регулярним виразом:
(а) a{a, b}*bb; (б) {a}*{b}*a{e, bb}*.
(а) Подія P – це множина всіх слів у алфавіті X = {a, b}, які починаються символом a та закінчуються парою символів bb.
(б) Будь-яке слово даної події починається з довільної кількості (зокрема 0) символів a, за якими йде довільна кількість символів b, і завершується або символом a, або підсловом abb.
4. Побудувати автомат, що розпізнає множину всіх слів у алфавіті {0, 1},
(а) що закінчуються на 00; (б) що містять три нулі поспіль; (в) що містять 01011 як підслово.
Нижче подано таблиці переходів таких автоматів. У кожному
з них початковим є перший стан, а заключним – останній. |
|
|||||||||||||||||||
|
|
(а) |
|
|
|
|
|
(б) |
|
|
|
|
|
(в) |
|
|
|
|||
|
δ |
1 |
|
2 |
3 |
|
δ |
1 |
|
2 |
3 |
4 |
|
δ |
1 |
2 |
3 |
4 |
5 |
6 |
|
0 |
2 |
|
3 |
3 |
|
0 |
2 |
|
3 |
4 |
4 |
|
0 |
2 |
2 |
4 |
2 |
4 |
2 |
|
1 |
1 |
|
1 |
1 |
|
1 |
1 |
|
1 |
1 |
4 |
|
1 |
1 |
3 |
1 |
5 |
6 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
219 |
|
|
|
|
|
|
|
|
Завдання для самостійної роботи
1.Нехай P, Q, R і S – події в алфавіті X. Довести, що коли P R
іQ S, то PQ RS. Чи правильним є обернене твердження?
2.Визначити всі можливі події P і Q в алфавіті {0, 1}, для яких PQ = {01, 010, 0101, 0111, 01000, 010111}.
3.Виписати всі слова події P*, довжина яких не перевищує k:
(а) P = {ab, b}, k = 5; |
(б) P = {a, ab, ba}, k = 7; |
(в) P = {aa, aba, baa}, k = 9. |
|
4. Скільки слів довжиною k містить подія, задана регулярним виразом r?
(а) r = (a b)*, k = 3; (б) r = (aa b)*, 3 ≤ k < 7; (в) r = (a b)*, k = n; (г) r = (aa b)*, k = n.
5.Довести, що коли P Q, то P* Q*.
6.Нехай P = {aa, ba} і Q = {aa, ba, aaaa}. Довести, що
P* = Q*.
7. Нехай P = {aa, ba} і Q = {aa, ba, aaa}. Довести, що
P* Q*.
8. Навести приклад таких подій P і Q, що:
(а) P Q, однак P* = Q*; (б) P* = Q*,
однак P Q (символ позначає, що не виконується жодне зі співвідношень , , , , =).
9. Нехай для непорожньої події P виконується рівність P2 = P. Довести, що: (а) e P; (б) P* = P.
10.Написати регулярний вираз у алфавіті X = {0, 1}, який задає подію, що складається зі всіх слів таких і тільки таких,
(а) у яких кількість символів 0 кратна 3; (б) які містять рівно 3 символи 1; (в) які закінчуються на 00 або на 11;
(г) які містять 00 або 11 тільки один раз; (д) які містять парну кількість 1; (е) у яких сьомим символом є 0;
(є) у яких третім символом від кінця є 1; (ж) у яких нулі утворюють підслова парної довжини.
11.Описати словами подію, задану регулярним виразом:
220