1.5.2 Подія в довільному алфавіті; подія, представлена в автоматному вiдображеннi лiтерою вихідного алфавіту; канонічна множина подій

Подією в довільному алфавіті Х називають довільну множину слів у даному алфавіті, а сам алфавіт Х – вхідним алфавітом зазначеної події.

Для будь-якого автоматного вiдображення φ iз вхідним алфавітом Х і вихідним алфавітом Y і для будь-якої вихідної лiтери уY, подію S_у, яка складається з усіх слів вхідного алфавіту, образи яких закінчуються лiтерою у, називають подією, представленою в автоматному вiдображеннi φ лiтерою вихідного алфавіту уY.

Множина подій S_{yi ,} де i = 1, …, m (у_і пробігає всі лiтери вихідного алфавіту Y) називається канонічною множиною подій, яка відповідає відображенню φ; також кажуть, що лiтера у_і позначає відповідну їй подію S_yi.

1.5.3 Теорема про зв'язок автоматного вiдображення φ iз відповідною йому канонічною множиною подій

Теорема. Будь-яке автоматне вiдображення φ однозначно визначається відповідною йому канонічною множиною подій.

Розглянемо доведення теореми.

Нехай: φ – довільне автоматне вiдображення; р = х_і1 . . . . х_ік – довільне вхідне слово; φ(р) = g = y_j1 . . . y_jk.

Покажемо, що g однозначно визначається задаванням канонічної множини подій _.

З даною метою, визначимо події множини М, в які входять початкові відрізки слова р.

В силу четвертої умови автоматності, такими подіями будуть події Sу_j1. . . .Sу_jk. ;задавання останніх дозволяє однозначно за індексами вказаних подій відновити вихідне слово φ(р)=g.

1.5.4 Алгебра подій

Будь-яке автоматне вiдображення φ може бути задане множиною М подій у вхідному алфавіті даного вiдображення.

Якщо область визначення автоматного вiдображення φ є скінченною, то всі події з множини М також є скінченними.

Скінченні події можна задавати, перерахувавши всі їх елементи.

Якщо область визначення автоматного вiдображення φ є нескінченною, то хоча б одна з подій множини М також буде нескінченною.

Тому необхідна така мова, що дозволяє описувати події з нескінченною множиною слів, i дану мову визначає введена С.К. Кліні алгебра подій.

Алгеброю подій в алфавіті Х називають множину всіх подій в даному алфавіті, над якою задані наступнi операції: диз’юнкція; множення; ітерація.

Диз’юнкцією S1  S2 двох подій S1 і S2 називається теоретико-множинне об’єднання даних подій.

Множенням S1S2 подій S1 і S2 називається подія, що складається зi всіх слів виду pq, де pS1, а qS2.

Ітерацією {S} події S називається подія, що складається з порожнього слова та всіх слів виду p₁…p_n, де p_i S, і= 1, .., n, n - довільне натуральне число.

Порядок виконання операцій в алгебрі подій (за відсутності дужок) є наступним: ітерація; множення; диз’юнкція.

1.6 Тотожності алгебри подій, видатні події, регулярнi вирази, циклiчна глибина регулярних виразiв i подiй, нескінченнi нерегулярнi події, теорема Кліні про зв’язок скінченних автоматів і регулярних подій

1.6.1 Тотожності в алгебрі подій

Операції в алгебрі подій вiдповiдають ряду наведених нижче тотожностей, які можна використовувати для перетворення та спрощення формул у даній алгебрі.

1. P  Q = Q  P

2. P  (Q  S) = (P  Q)  S

3. P  P = P

4. P (QS) = (PQ) S

5. P (Q  S) = PQ  PS (P  Q) S = PS  QS

6. {{P}} = {P}

7. {P} = e v P {P}

8. P{P} = {P} P

9. {P}{P} = {P}

10. {P}  P = {P}

11. eS = Se = S

12. {e} = e

У наведеному вище перелiку: P, Q i S позначають довільні події; е позначає подію, що складається з одного порожнього слова.

Відзначимо, що операція множення в алгебрі подій не є комутативною, тобто, у загальному випадку: PQ ≠ QP.

1.6.2 Видатні події (загальна подія, неможлива або порожня подія; одноелементна подія; скінченна подія; елементарна подія; регулярна подія)

Перерахуємо деякі видатні події, з якими будемо мати справу надалi.

Загальна подія містить у собі всі слова в даному алфавіті.

Неможлива або порожня подія не містить жодного слова (в тому числi, і порожнього).

Одноелементна подія складається з одного слова.

Скінченна подія складається зi скінченної множини слів.

Елементарна подія в алфавіті X={x₁,…,x_n} є (n+1)-одноелементною подією x₁, …, x_n , е, де е - порожнє слово.

Регулярну подію можна отримати з елементарних подій застосуванням скінченного числа операцій ітерації, множення та диз’юнкції.

1.6.3 Регулярний вираз, циклічна глибина регулярного виразу та регулярної події

Регулярним виразом називають подання регулярної події через елементарні події та операції ітерації, множення та диз’юнкції.

Одна і та ж сама подія допускає багато різних представлень.

Циклічною глибиною регулярного виразу називають максимальне число вкладених пар ітераційних дужок, з яких складається даний вираз.

Наприклад: регулярний вираз x {y  {x} } має циклічну глибину 2 (складається з двох пар ітераційних дужок), а вираз x  yz - циклічну глибину 0.

Циклічною глибиною регулярної події називають найменшу циклічну глибину регулярних виразів, якi представляють дану подію.

Твердження: скінченні події та тільки вони є регулярними подіями, що мають нульову циклічну глибину.

Наслідок: лише використання ітерації дозволяє будувати регулярні вирази для нескінченних подій.

У той самий час, не всі нескінченні події є регулярними.

1.6.4 Приклад С.К. Кліні нескінченної нерегулярної події

Приклад нескiнченної нерегулярної події першим навів С.К.Кліні.

Таким прикладом є подія S, яка складається зі всіх слів у кінцевому алфавіті X, довжини яких є точними квадратами (тобто слова події S мають довжину 1, 4, 9, 16, 25 тощо).

1.6.5 Теорема Кліні про зв’язок скінченних автоматів і регулярних подій, наслідок теореми Кліні

Теорема Кліні (про зв’язок кінцевих автоматів і регулярних подій). Нехай задано деяку множину М подій S₁,…,S_n у деякому кінцевому алфавіті Х. Кожна з подій множини М тоді та тільки тоді може бути представлена в кінцевому автоматі деякою множиною його станів або вихідних сигналів, коли кожна з подій множини М є регулярною подією.

Наслідок теореми Клiнi. Умова, яку необхідно накласти на нескінченну область визначення алфавітного оператору для того, щоб можна було побудувати кінцевий автомат, який реалізує даний алфавітний оператор, полягає в тому, що вказана область визначення повинна бути регулярною подією.

1.7 Структурна теорія автоматів