✖

Wyrażenia regularne

Kapitoly: Wyrażenia regularne, Wyrażenie regularne na automat, Uogólniony NFA, Automat na wyrażenie regularne

Wyrażenie regularne to napis, który pozwala opisać pewien zbiór słów. Wyrażenia regularne możemy też traktować jako prosty sposób opisania automatu skończonego.

Co to jest wyrażenie regularne

W arytmetyce używamy symboli takich jak · i +, żeby zbudować wyrażenie, na przykład (2 + 3) · 4. Obliczając wartość tego wyrażenia, dostaniemy liczbę. Wyrażenie regularne to pewien ciąg znaków i kilku symboli specjalnych (np. a(x∪ y)), którego wartością jest język (formalny). Wynikiem wyrażenia (2 + 3) · 4 jest liczba 20, wynikiem wyrażenia regularnego a(x∪ y) jest zbiór dwóch słów „ax”, „ay”.

Jak obliczylibyśmy wartość poprzedniego wyrażenia regularnego a(x∪ y)? Każda litera jest w rzeczywistości skrótem dla jednoelementowego zbioru zawierającego tę literę, a ukryte mnożenie to konkatenacja słów. Wyrażenie regularne moglibyśmy zapisać „w pełnej postaci” tak:

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

Dalej obliczylibyśmy je tak: suma {x}∪{y} daje nam język {x,y}. Konkatenacją języków {a} i {x,y} dostaniemy język {ax, ay}.

Wyrażenia regularne bardzo często używa się w programowaniu i większość języków programowania ma wyrażenia regularne w jakiś sposób zaimplementowane. Używa się ich na przykład do sprawdzania, czy tekst wpisany przez użytkownika spełnia określone kryteria (np. czy jest to poprawny adres e-mail, poprawna data itp.), a także do zastępowania tekstów (np. możemy chcieć zamienić wszystkie adresy URL w tekście na klikalne odnośniki itp.).

Rzeczywiste implementacje wyrażeń regularnych są zwykle silniejsze niż opisane tutaj wyrażenia regularne i używają nieco innej, a przede wszystkim bardziej skomplikowanej składni.

Definicja wyrażenia regularnego

Wyrażenie regularne będziemy definiować nad pewnym alfabetem $\Sigma$. Powiemy, że wyrażeniem regularnym jest:

  1. a, gdzie $a \in \Sigma$. Czyli sam znak alfabetu jest wyrażeniem regularnym.
  2. ε: słowo puste, w programowaniu zapisuje się je też jako pusty napis \“\“.
  3. ∅: wyrażenie regularne musi umieć opisać także język pusty, więc język pusty jest wyrażeniem regularnym.
  4. (R1 ∪ R2), gdzie R1, R2 są wyrażeniami regularnymi.
  5. $(R_1 \circ R_2)$, gdzie R1, R2 są wyrażeniami regularnymi.
  6. $(R^\ast)$, gdzie R jest wyrażeniem regularnym.

Zamiast symbolu ∪ z punktu 4 możemy też używać symbolu pionowej kreski: |. Zamiast symbolu $\circ$ nie musimy używać niczego. Podobnie jak zwykle nie piszemy wprost symbolu mnożenia, kropki · , tak zwykle nie piszemy też symbolu konkatenacji $\circ$. Te wyrażenia regularne są więc identyczne: $a\circ (b\cup c)$ i a(b|c).

Co oznaczają poszczególne operatory?

  • ∪ albo | oznacza sumę języków.
  • $\circ$ oznacza konkatenację języków.
  • $^\ast$ oznacza domknięcie Kleene’ego języka.

Przykłady:

  • a oznacza prosty język {a}.
  • a|b oznacza język składający się z dwóch słów {a, b}.
  • $a\circ b$ oznacza język {ab}.
  • a(b|c)d oznacza język {abd, acd}.
  • $a(b^\ast)$ oznacza język wszystkich słów, które zaczynają się literą „a”, po której następuje dowolna liczba liter „b”.
  • $(ab)^\ast$ oznacza język wszystkich słów {ε, ab, abab, ababab, …}.
  • $0^\ast10^\ast$ oznacza język wszystkich słów binarnych, które zawierają dokładnie jedną jedynkę. (Zauważ, że dokładniej byłoby zapisać to wyrażenie tak: $(0^\ast)1(0^\ast)$, ale skoro zapis jest czytelny i bez tego, możemy nawiasy pominąć.)
  • $\Sigma^\ast1\Sigma^\ast$ oznacza język wszystkich słów zawierających co najmniej jedną jedynkę.
  • $(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^\ast$ oznacza język wszystkich dodatnich liczb naturalnych zapisanych bez zer na początku.

Dalej pokażemy równoważność wyrażeń regularnych i automatów skończonych. Dla każdego wyrażenia regularnego, którego wartością jest język R, istnieje automat skończony A, dla którego zachodzi L(A) = R, i odwrotnie.

Źródła