✖

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

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

Какво е регулярен израз

В аритметиката използваме символи като · и +, за да съставим израз като например (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, и обратно.

Източници

Глави: Регулярни изрази, Преобразуване на регулярен израз в автомат, Обобщен недетерминиран краен автомат, Преобразуване на автомат в регулярен израз