4. Zbiory regularne, automaty skończone
4.1. Zbiory regularne, wyrażenia regularne
Zbiory regularne
Niech T będzie alfabetem.
Zbiór regularny nad alfabetem T definiujemy następująco:
-
– zbiór pusty jest zbiorem regularnym,
-
{} – zbiór zawierający łańcuch pusty jest zbiorem regularnym,
-
{a | a T} – zbiór zawierający łańcuch złożony z pojedynczego symbolu alfabetu jest zbiorem regularnym,
-
jeśli P i Q są zbiorami regularnymi nad T to zbiorami regularnymi są także:
-
P Q – suma teoriomnogościowa zbiorów P i Q,
-
PQ – złożenie (konkatenacja) zbiorów P i Q,
-
P* - domknięcie Kleene’ego zbioru P.
-
nic innego poza tym, co wynika z punktów (1) – (4), nie jest zbiorem regularnym.
Przykład:
Niech T = {a, b}. Zbiorem regularnym nad T jest np. zbiór:
{, a, ab, abb, abbb, abbbb, ...} = {} {a}{b}*
Wyrażenia regularne
Wyrażenia regularne służą do uproszczonego oznaczania zbiorów regularnych.
Niech T będzie alfabetem.
Wyrażenia regularne nad alfabetem T definiujemy następująco:
-
– jest wyrażeniem regularnym oznaczającym zbiór pusty będący zbiorem regularnym,
-
– jest wyrażeniem regularnym oznaczającym zbiór zawierający łańcuch pusty {} będący zbiorem regularnym,
-
a – jest wyrażeniem regularnym oznaczającym zbiór {a | a T} zawierający łańcuch złożony z pojedynczego symbolu alfabetu będący zbiorem regularnym,
-
jeśli p i q są wyrażeniami regularnymi oznaczającymi odpowiednio zbiory regularne P i Q nad T to wyrażeniami regularnymi są także:
-
p|q – wyrażenie regularne oznaczające P Q – sumę teoriomnogościową zbiorów P i Q będącą zbiorem regularnym,
-
pq – wyrażenie regularne oznaczające PQ – złożenie (konkatenację) zbiorów P i Q będące zbiorem regularnym,
-
p* - wyrażenie regularne oznaczające P* - domknięcie Kleene’ego zbioru P będące zbiorem regularnym.
-
nic innego poza tym, co wynika z punktów (1) – (4), nie jest wyrażeniem regularnym.
Przykład:
Niech T = {a, b}. Zbiór regularny nad T :
{, a, ab, abb, abbb, abbbb, ...} = {} {a}{b}*
zapisujemy jako |ab*.
Przykład:
(0|1)*011 odpowiada zbiorowi
({0} {1})* {0}{1}{1} = {0, 1}* {011}
będącemu dowolnym ciągiem zer i jedynek zakończonym sekwencją: 011.
Dwa wyrażenia p i q regularne są równe (równoważne), gdy odpowiadające im zbiory regularne P i Q są równe (identyczne).
Zapisując wyrażenia regularne stosujemy następujące priorytety operatorów:
-
( ) - najwyższy,
-
*
-
∙ - (konkatenacja)
-
| - najniższy.
Niech p, q i r będą dowolnymi wyrażeniami regularnymi. Prawdziwe są następujące zależności i tożsamości:
p|q = q|p
p|(q|r) = (p|q)|r
p(qr) = (pq)r
pq|pr = p(q|r)
pq|rq = (p|r)q
p = p = p
p = p =
* =
* =
p* = p|p* = (p|)*
(p*)* = p*
p|p = p
p| = p
|p* = p*
|pp* = p*
|p*p = p*
pqq*|pq* = pq*
(p|q)* = (p*|q*)* = (p*q*)*
Przykład:
abb*|ab* = ab*
bo:
abb*|ab* = {ab}{b}* {a}{b}* = {ab, abb, abbb, ...} {a, ab, abb, ...} =
= {a, ab, abb, ...} = {a}{b}*
Zbiory regularne nazywamy też językami regularnymi.
|