Регулярні події та вирази
Матеріал з Вікіпедії — вільної енциклопедії.
Регулярні події та вирази — події, представимі в скінченних автоматах, і відповідні вирази в спеціальній алгебраїчній мові, яка задає ці події.
Зміст |
[ред.] Теоретичні відомості
Подією називається довільна множина слів в деякому алфавіті. Природньо, що при вивченні теорією автоматів різноманітних питань, пов'язаних з поняттям події, як правило припускається наявність деяких засобів для описання (визначення) подій. Таким конструктивним засобом може бути формальна мова, вирази якої задають події над деяким алфавітом (тобто, формальна мова інтерпретується в множину подій). Якщо позначити цю мову через L, то правильно побудовані вирази можна називати L-виразами, а події, які вони задають, — L-подіями. Очевидно, що множина всіх L-подій для будь якої мови L не більш ніж лічима, так як множина відповідних виразів не більш ніж злічима. Так як потужність множини всіх подій континуальна, то нема такої мови L, для якої всі події є L-подіями.
Для теорії автоматів притаманний наступний підхід. Фіксується деякий клас автоматів K. Ставиться задача: побудувати мову L (як правило, таку, що не використовує автоматних понять, зручну в тому чи іншому відношенні, що задовільняє певним вимогам, і т. д.), таку, що всі L події, і тільки вони представимі в автоматах класу K.
Розв'язання цієї задачі включає доведення двох теорем:
- теореми синтезу (кожна L-подія представима в деякому автоматі класу K)
- теореми аналізу (кожна подія, представима в автоматі класу K, є L-подією).
Як правило, теорема синтезу одразу припускає наявність алгоритму синтезу, тобто, алгоритму побудови автомату по заданій події, а теорема аналізу — алгоритму аналізу, тобто, алгоритма побудови L-виразу по заданому автомату.
Вперше такий підхід в теорії автоматів застосував американський математик Кліні С. К., для класу скічнених автоматів. Для подій, представимих в скінчених автоматах, він побудував спеціальну мову — мову регулярних виразів. Ця мова стала однією із основних мов для визначення умов функціонування автомату, особливо після його вдосконалення (а також відповідних алгоритмів синтезу та аналізу) в працях радянського математика Глушкова В. М., та американського математика Мак-Нотона Р. Ф., і інших дослідників.
[ред.] Побудова алгебраїчної мови
Алгебраїчна мова будується як мова виразів деякої алгебри. В цьому випадку розглядається мова для описання подій, тому множина всіх подій представляє собою деяку універсальну алгебру, тобто, над подіями визначаються алгебраїчні операції. Для побудови мови регулярних виразів було використано три операції над подіями (дві бінарні і одна унарна):
- A ∨ B — диз'юнкція або об'єднання (позначається також A ∪ B) — теоретико множинна операція: подія A ∨ B представляє собою звичайне об'єднання множин A та B;
- AB — добуток (конкатенація), визначається через добуток слів. Добутком слів p та q називають слово pq, утворене в результаті дописування слова q справа до слова p. Подія AB складається із тих і тільки тих слів, які мають вигляд pq, де p належить A, а q належить B;
- {A} — ітерація (позначається також A*).
Ітерація визначається трохи складніше. Введемо позначення An для добутку
. Тоді ітерацію можна виразити через попередні дві операції наступним чином:
- {A} = A ∨ A2 ∨ ... ∨ An ∨ ...
Таким чином, слово q тоді і тільки тоді належить {A}, коли q має вигляд pn, де p — належить A.
Нехай алфавіт X, над яким розглядаються події, складається із літер x1, x2, ..., xm, тоді подія, яка складається із одного однолітерного слова xi (i = 1, 2, ..., m), називається елементарною подією і позначається символом xi, тобто, відповідає одній літері алфавіту.
[ред.] Регулярні вирази
Вираз, побудований із літер алфавіту X (символів елементарних подій) і із символів операцій диз'юнкції, добутку і ітерації з використанням відповідним чином круглих дужок, називається регулярним виразом в алфавіті X.
Будь який регулярний вираз R визначає деяку подію S (S отримується в результаті виконання всіх операцій, які входять в вираз R). Події, які визначаються в такий спосіб, називаються регулярними подіями над алфавітом X. Іншими словами, регулярною подією називається подія, отримана із елементарних, із допомогою застосування скінченої кількості раз операції диз'юнкції, добутку і ітерації.
Регулярні події і тільки вони представимі в скінчених автоматах.
[ред.] Приклад застосування
Наприклад, в алфавіті із трьох літер x, y, z, регулярний вираз
- x { x ∨ y ∨ z} (y ∨ z)
визначає подію (регулярну), яка складається із всіх слів, які починаються на літеру x і закінчуються літерою y або z.
В сучасних мовах програмування, наприклад, Perl, аналогічний вираз міг би мати вигляд:
^x[xyz]*[yz]$
[ред.] Джерела інформації
- Енциклопедія кібернетики, т. 2, с. 285.
[ред.] Дивіться також
- Алгебраїчна теорія автоматів
- Алгебра подій
- Універсальні алгебри
- Регулярні вирази (програмування)
| Це незавершена стаття з математики. Ви можете допомогти проекту, виправивши або дописавши її. |

