Równoważność wzorców      
i wyrażeń regularnych

Kamila Borucka
Paweł Barud

Wydział Inżynierii Mechanicznej i Robotyki

Katedra Automatyzacji Procesów

09.06.2015 r.

Wzorce

• Wzorzec to zbiór obiektów o pewnej rozpoznawalnej 

właściwości.

• Może to być:

– zbiór ciągów znaków, taki jak zbiór poprawnych 

identyfikatorów języka C, z których każdy stanowi ciąg 
znakowy, składający się z liter, cyfr i znaków 
podkreślenia oraz rozpoczyna się od litery lub znaku 
podkreślenia.

– zbiór tablic zer i jedynek o danym rozmiarze, które 

czytnik znaków może interpretować jako reprezentację 
tego samego symbolu. Zbiór wszystkich takich tablic 
stanowiłby wzorzec o nazwie „A”.

Przykładowe wzorce

• [0-9]+ opisuje (niepuste) ciągi cyfr, czyli zapisy 

dziesiętne liczb naturalnych.

• Do wzorca  (a*bba*) ∩ (ab | ba)* pasuje tylko słowo abba. 

Do a*bba* pasują słowa zawierające dokładnie dwie litery 
b i to położone obok siebie, a do  (ab | ba) pasują słowa 
zbudowane z ,,cegiełek'' ab i ba. Jedynym słowem, które 
pasuje do obydwu tych wzorców jest właśnie abba.

• Wzorzec [A-Z][A-Z] [0-9][0-9][0-9][0-9][0-9] opisuje jedną 

z form numerów rejestracyjnych, złożonych z dwóch liter i 
pięciu cyfr.

3 równoważne opisy wzorców

• oparty na teorii grafów, polegać będzie na wykorzystaniu 

ścieżek w grafie szczególnego rodzaju, który nazwiemy 
automatem,

• o charakterze algebraicznym, wykorzystujący notacje 

wyrażeń regularnych,

• oparty o wykorzystanie definicji rekurencyjnych, nazwany 

gramatyką bezkontekstową.

Wyrażenia regularne

• Wyrażenia regularne (ang. regular expressions, w skrócie 

regex lub regexp) – stanowią algebraiczny sposób 
definiowania wzorców. Teoria wyrażeń regularnych jest 
związana z teorią języków regularnych. 

• Wyrażenia regularne stanowią analogię do algebry 

wyrażeń arytmetycznych oraz do algebry relacyjnej.

• Zbiór wzorców, które można wyrazić w ramach algebry 

wyrażeń regularnych odpowiada dokładnie zbiorowi 
wzorców, które można opisać za pomocą automatów.

Wyrażenia regularne

• Wyrażenia regularne posiadają pewne rodzaje operandów 

niepodzielnych (ang. atomic operands): Znak, Symbol ɛ, 
Symbol Φ oraz Zmienna - może być ona dowolnym 
wzorcem zdefiniowanym za pomocą wyrażenia 
regularnego.

• Wartość wyrażenia regularnego jest wzorcem 

składającym się ze zbioru ciągów znaków, który często 
określa się mianem języka (ang. language). 

• Językiem regularnym nazywamy każdy język formalny L 

nad danym alfabetem, dla którego istnieje wyrażenie 
regularne A takie, że: L=L(A) . Klasę języków regularnych 
oznaczamy przez JR. 

Wyrażenia regularne

Każdy język regularny może być generowany przez wiele wyrażeń 
regularnych. Mówimy, że wyrażenia regularne A i B są równoważne, 
gdy generują ten sam język, tzn.

A≡B↔L(A)=L(B)

Tw. Dla dowolnych wyrażeń regularnych A, B, C nad alfabetem Σ 
zachodzą następujące równoważności:

Przykład

Przykład

Przykład