Подією в довільному алфавіті Х називають довільну множину слів у даному алфавіті, а сам алфавіт Х – вхідним алфавітом зазначеної події.
Для будь-якого автоматного вiдображення φ iз вхідним алфавітом Х і вихідним алфавітом Y і для будь-якої вихідної лiтери уÎY, подію Sу, яка складається з усіх слів вхідного алфавіту, образи яких закінчуються лiтерою у, називають подією, представленою в автоматному вiдображеннi φ лiтерою вихідного алфавіту уÎY.
Множина подій Syi , де i = 1, …, m (уі пробігає всі лiтери вихідного алфавіту Y) називається канонічною множиною подій, яка відповідає відображенню φ; також кажуть, що лiтера уі позначає відповідну їй подію Syi.
1.5.3 Теорема про зв'язок автоматного вiдображенняφiз відповідною йому канонічною множиною подій
Теорема. Будь-яке автоматне вiдображенняφ однозначно визначається відповідною йому канонічною множиною подій.
Розглянемо доведення теореми.
Нехай: φ – довільне автоматне вiдображення; р = хі1 . . . . хік – довільне вхідне слово; φ(р) = g = yj1 . . . yjk.
Покажемо, що 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 називається подія, що складається з порожнього слова та всіх слів виду p1…pn, де pi Î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 скінченної множини слів.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.