Wyrażenia 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:
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 Σ. Powiemy, że wyrażeniem regularnym jest:
- a, gdzie a ∈ Σ. Czyli sam znak alfabetu jest wyrażeniem regularnym.
- ϵ: słowo puste, w programowaniu zapisuje się je też jako pusty napis „”.
- ∅: wyrażenie regularne musi umieć opisać także język pusty, więc język pusty jest wyrażeniem regularnym.
- (R1 ∪ R2), gdzie R1, R2 są wyrażeniami regularnymi.
- (R1 ∘ R2), gdzie R1, R2 są wyrażeniami regularnymi.
- (R∗), gdzie R jest wyrażeniem regularnym.
Zamiast symbolu ∪ z punktu 4 możemy też używać symbolu pionowej kreski: |. Zamiast symbolu ∘ nie musimy używać niczego. Podobnie jak zwykle nie piszemy wprost symbolu mnożenia, kropki ·, tak zwykle nie piszemy też symbolu konkatenacji ∘. Te wyrażenia regularne są więc identyczne: a ∘ (b ∪ c) i a(b|c).
Co oznaczają poszczególne operatory?
- ∪ albo | oznacza sumę języków.
- ∘ oznacza konkatenację języków.
- ∗ 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 ∘ b oznacza język {ab}.
- a(b|c)d oznacza język {abd, acd}.
- a(b∗) oznacza język wszystkich słów, które zaczynają się literą „a”, po której następuje dowolna liczba liter „b”.
- (ab)∗ oznacza język wszystkich słów {ϵ, ab, abab, ababab, …}.
- 0∗10∗ 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∗)1(0∗), ale skoro zapis jest czytelny i bez tego, możemy nawiasy pominąć.)
- Σ∗1Σ∗ 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)∗ 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
Rozdziały: Wyrażenia regularne, Wyrażenie regularne na automat, Uogólniony NFA, Automat na wyrażenie regularne