✖

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

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

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

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

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

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

$$ \left\{a\right\}\circ\left(\left\{x\right\}\cup\left\{y\right\}\right) $$

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

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

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

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

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

  1. a, де $a \in \Sigma$. Тобто окремий символ алфавіту є регулярним виразом.
  2. ε: порожнє слово; у програмуванні його також записують як порожні лапки ““.
  3. ∅: регулярний вираз має вміти описувати й порожню мову, тому порожня мова теж є регулярним виразом.
  4. (R1 ∪ R2), де R1, R2 — регулярні вирази.
  5. $(R_1 \circ R_2)$, де R1, R2 — регулярні вирази.
  6. $(R^\ast)$, де R — регулярний вираз.

Замість символу ∪ з пункту 4 можна також використовувати вертикальну риску: |. Замість символу $\circ$ можна не писати нічого. Так само як знак множення, крапку · , здебільшого не пишуть, зазвичай не пишуть і символ конкатенації $\circ$. Тому ці регулярні вирази однакові: $a\circ (b\cup c)$ і a(b|c).

Що означають окремі оператори?

  • ∪ або | позначає об'єднання мов.
  • $\circ$ позначає конкатенацію мов.
  • $^\ast$ позначає замикання Кліні мови.

Приклади:

  • a позначає найпростішу мову {a}.
  • a|b позначає мову з двох слів {a, b}.
  • $a\circ b$ позначає мову {ab}.
  • a(b|c)d позначає мову {abd, acd}.
  • $a(b^\ast)$ позначає мову всіх слів, які починаються буквою «a», після якої йде довільна кількість букв «b».
  • $(ab)^\ast$ позначає мову всіх слів {ε, ab, abab, ababab, …}.
  • $0^\ast10^\ast$ позначає мову всіх двійкових слів, що містять рівно одну одиницю. (Зауваж, що точніше було б записати цей вираз так: $(0^\ast)1(0^\ast)$, але якщо запис зрозумілий і без цього, дужки можна опустити.)
  • $\Sigma^\ast1\Sigma^\ast$ позначає мову всіх слів, що містять принаймні одну одиницю.
  • $(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^\ast$ позначає мову всіх натуральних чисел.

Далі покажемо еквівалентність регулярних виразів і скінченних автоматів. Для кожного регулярного виразу, результатом обчислення якого є мова R, існує скінченний автомат A, для якого виконується L(A) = R, і навпаки.

Джерела