✖

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

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

Що таке регулярний вираз

В арифметиці ми використовуємо символи, як-от · і +, щоб скласти вираз, наприклад (2 + 3) · 4. Обчисливши цей вираз, отримуємо число. Регулярний вираз — це послідовність символів і кількох спеціальних знаків, наприклад a(x ∪ y), і результатом його обчислення є (формальна) мова. Результатом виразу (2 + 3) · 4 є число 20, а результатом регулярного виразу a(x ∪ y) є множина з двох слів «ax», «ay».

Як обчислити попередній регулярний вираз a(x ∪ y)? Кожна буква насправді є скороченим записом одноелементної множини, що містить цю букву, а прихований знак множення — це конкатенація слів. Регулярний вираз можна переписати «повністю» так:

{a}∘({x}∪{y})

Далі обчислюємо так: об'єднання {x} ∪ {y} дає мову {x,y}. Конкатенація мов {a} і {x,y} дає мову {ax, ay}.

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

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

Означення регулярного виразу

Регулярний вираз означуватимемо над деяким алфавітом Σ. Тоді регулярним виразом називаємо:

  1. a, де a ∈ Σ. Тобто окремий символ алфавіту є регулярним виразом.
  2. ϵ: порожнє слово; у програмуванні його також записують як порожні лапки «».
  3. ∅: регулярний вираз має вміти описувати й порожню мову, тому порожня мова теж є регулярним виразом.
  4. (R1 ∪ R2), де R1, R2 — регулярні вирази.
  5. (R1 ∘ R2), де R1, R2 — регулярні вирази.
  6. (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, і навпаки.

Джерела

Розділи: Регулярні вирази, Регулярний вираз → автомат, Узагальнений НСА, Автомат → регулярний вираз