Регулярні вирази
Регулярний вираз — це текстовий рядок, який дає змогу описати певну множину слів. Регулярні вирази можна також розглядати як простий спосіб описати скінченний автомат.
Що таке регулярний вираз
В арифметиці ми використовуємо символи, як-от · і +, щоб скласти вираз, наприклад (2 + 3) · 4. Обчисливши цей вираз, отримуємо число. Регулярний вираз — це послідовність символів і кількох спеціальних знаків, наприклад a(x ∪ y), і результатом його обчислення є (формальна) мова. Результатом виразу (2 + 3) · 4 є число 20, а результатом регулярного виразу a(x ∪ y) є множина з двох слів «ax», «ay».
Як обчислити попередній регулярний вираз a(x ∪ y)? Кожна буква насправді є скороченим записом одноелементної множини, що містить цю букву, а прихований знак множення — це конкатенація слів. Регулярний вираз можна переписати «повністю» так:
Далі обчислюємо так: об'єднання {x} ∪ {y} дає мову {x,y}. Конкатенація мов {a} і {x,y} дає мову {ax, ay}.
Регулярні вирази дуже часто використовують у програмуванні, і більшість мов програмування так чи інакше їх реалізує. Регулярні вирази застосовують, наприклад, для перевірки того, чи введений користувачем текст відповідає певним умовам (скажімо, чи це допустима електронна адреса або дата), а також для заміни фрагментів тексту (наприклад, можна замінити всі URL у тексті на клікабельні посилання).
Реальні реалізації регулярних виразів зазвичай потужніші за описані тут і використовують трохи інший, але насамперед складніший синтаксис.
Означення регулярного виразу
Регулярний вираз означуватимемо над деяким алфавітом Σ. Тоді регулярним виразом називаємо:
- a, де a ∈ Σ. Тобто окремий символ алфавіту є регулярним виразом.
- ϵ: порожнє слово; у програмуванні його також записують як порожні лапки «».
- ∅: регулярний вираз має вміти описувати й порожню мову, тому порожня мова теж є регулярним виразом.
- (R1 ∪ R2), де R1, R2 — регулярні вирази.
- (R1 ∘ R2), де R1, R2 — регулярні вирази.
- (R∗), де R — регулярний вираз.
Замість символу ∪ з пункту 4 можна також використовувати вертикальну риску: |. Замість символу ∘ можна не писати нічого. Так само як знак множення, крапку ·, здебільшого не пишуть, зазвичай не пишуть і символ конкатенації ∘. Тому ці регулярні вирази однакові: a ∘ (b ∪ c) і a(b|c).
Що означають окремі оператори?
- ∪ або | позначає об'єднання мов.
- ∘ позначає конкатенацію мов.
- ∗ позначає замикання Кліні мови.
Приклади:
- a позначає найпростішу мову {a}.
- a|b позначає мову з двох слів {a, b}.
- a ∘ b позначає мову {ab}.
- a(b|c)d позначає мову {abd, acd}.
- a(b∗) позначає мову всіх слів, які починаються буквою «a», після якої йде довільна кількість букв «b».
- (ab)∗ позначає мову всіх слів {ϵ, ab, abab, ababab, …}.
- 0∗10∗ позначає мову всіх двійкових слів, що містять рівно одну одиницю. (Зауваж, що точніше було б записати цей вираз так: (0∗)1(0∗), але якщо запис зрозумілий і без цього, дужки можна опустити.)
- Σ∗1Σ∗ позначає мову всіх слів, що містять принаймні одну одиницю.
- (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ позначає мову всіх натуральних чисел.
Далі покажемо еквівалентність регулярних виразів і скінченних автоматів. Для кожного регулярного виразу, результатом обчислення якого є мова R, існує скінченний автомат A, для якого виконується L(A) = R, і навпаки.
Джерела
Розділи: Регулярні вирази, Регулярний вираз → автомат, Узагальнений НСА, Автомат → регулярний вираз