Регулярна граматика

Регулярна граматика — формальна граматика типу 3 за ієрархією Чомскі. Регулярні граматики визначають в точності всі регулярні мови, і тому еквівалентні кінцевим автоматам і регулярним виразами. Регулярні граматики є підмножиною контекстно-вільних.

Регулярні події та вирази — це події, що можна представити у скінченних автоматах, а також відповідні вирази, складені за спеціальною алгебричною мовою (регулярна мова), яка задає ці події.

Теоретичні відомості

Подією називається довільна множина слів в деякому алфавіті. Природно, що при вивченні теорією автоматів різноманітних питань, пов'язаних з поняттям події, як правило припускається наявність деяких засобів для описання (визначення) подій. Таким конструктивним засобом може бути формальна мова, вирази якою задають події над деяким алфавітом (тобто, формальна мова інтерпретується в множину подій). Якщо позначити цю мову через L, то правильно побудовані вирази можна називати L-виразами, а події, які вони задають, — L-подіями. Очевидно, що множина всіх L-подій для будь-якої мови L не більш ніж лічима, оскільки множина відповідних виразів не більш ніж злічима. Оскільки потужність множини всіх подій континуальна, то нема такої мови L, для якої всі події є L-подіями.

Для теорії автоматів притаманний наступний підхід. Фіксується деякий клас автоматів K. Ставиться задача: побудувати мову L (як правило, таку, що не використовує автоматних понять, зручну в тому чи іншому відношенні, що задовольняє певним вимогам, і т. д.), таку, що всі L події, і тільки вони представимі в автоматах класу K.

Розв'язання цієї задачі включає доведення двох теорем:

• теореми синтезу (кожна L-подія представима в деякому автоматі класу K)
• теореми аналізу (кожна подія, представима в автоматі класу K, є L-подією).

Як правило, теорема синтезу одразу припускає наявність алгоритму синтезу, тобто, алгоритму побудови автомата за заданою подією, а теорема аналізу — алгоритму аналізу, тобто, алгоритму побудови L-виразу за заданим автоматом.

Вперше такий підхід в теорії автоматів застосував американський математик Кліні С. К., для класу скічненних автоматів. Для подій, представимих в скінченних автоматах, він побудував спеціальну мову — мову регулярних виразів. Ця мова стала однією із основних мов для визначення умов функціонування автомату, особливо після його вдосконалення (а також відповідних алгоритмів синтезу та аналізу) в працях радянського математика Глушкова В. М., та американського математика Мак-Нотона Р. Ф., і інших дослідників.

Побудова алгебраїчної мови

Алгебраїчна мова будується як мова виразів деякої алгебри. В цьому випадку розглядається мова для описання подій, тому множина всіх подій являє собою деяку універсальну алгебру, тобто, над подіями визначаються алгебраїчні операції. Для побудови мови регулярних виразів було використано три операції над подіями (дві бінарні і одна унарна):

1. A ∨ B — диз'юнкція або об'єднання (позначається також A ∪ B) — теоретико множинна операція: подія A ∨ B являє собою звичайне об'єднання множин A та B;
2. AB — добуток (конкатенація), визначається через добуток слів. Добутком слів p та q називають слово pq, утворене в результаті дописування слова q справа до слова p. Подія AB складається із тих і тільки тих слів, які мають вигляд pq, де p належить A, а q належить B;
3. {A} — ітерація (позначається також A^*).

Ітерація визначається трохи складніше. Введемо позначення Aⁿ для добутку ${\begin{matrix}\underbrace {AA\dots A} \\n\end{matrix}}$. Тоді ітерацію можна висловити через попередні дві операції так:

{A} = A ∨ A² ∨ … ∨ Aⁿ ∨ …

Таким чином, слово q тоді і тільки тоді належить {A}, коли q має вигляд pⁿ, де p — належить A.

Нехай алфавіт X, над яким розглядаються події, складається із літер x₁, x₂, …, x_m, тоді подія, яка складається із одного однолітерного слова x_i (i = 1, 2, …, m), називається елементарною подією і позначається символом x_i, тобто, відповідає одній літері алфавіту.

Регулярні вирази

Вираз, побудований із літер алфавіту X (символів елементарних подій) і із символів операцій диз'юнкції, добутку і ітерації з використанням відповідним чином круглих дужок, називається регулярним виразом в алфавіті X.

Будь-який регулярний вираз R визначає деяку подію S (S отримується в результаті виконання всіх операцій, які входять у вираз R). Події, які визначаються в такий спосіб, називаються регулярними подіями над алфавітом X. Іншими словами, регулярною подією називається подія, отримана із елементарних, із допомогою застосування скінченої кількості раз операції диз'юнкції, добутку і ітерації.

Регулярні події і тільки вони представимі в скінчених автоматах.

Приклад застосування

Наприклад, в алфавіті із трьох літер x, y, z, регулярний вираз

x { x ∨ y ∨ z} (y ∨ z)

визначає подію (регулярну), яка складається із всіх слів, які починаються на літеру x і закінчуються літерою y або z.

У сучасних мовах програмування, наприклад, Perl, аналогічний вираз міг би мати вигляд:

^x[xyz]*[yz]$

Див. також

• Алгебраїчна теорія автоматів
• Алгебра подій
• Універсальні алгебри
• Регулярний вираз
• Алгоритми визначення регулярності граматики
• Програмування
• Глибина циклічної події

Джерела

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973. — Т. 2. — С. 285.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)