To tylko jedna z 3 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
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:
(1) ∅ – zbiór pusty jest zbiorem regularnym,
(2) {ε} – zbiór zawierający łańcuch pusty jest zbiorem regularnym,
(3) {a | a ∈ T} – zbiór zawierający łańcuch złożony z pojedynczego symbolu alfabetu
jest zbiorem regularnym,
(4) jeśli P i Q są zbiorami regularnymi nad T to zbiorami regularnymi są także:
(a) P ∪ Q – suma teoriomnogościowa zbiorów P i Q,
(b) PQ – złożenie (konkatenacja) zbiorów P i Q,
(c) P* - domknięcie Kleene’ego zbioru P.
(5) 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:
(1) ∅ – jest wyrażeniem regularnym oznaczającym zbiór pusty ∅ będący zbiorem
regularnym,
(2) ε – jest wyrażeniem regularnym oznaczającym zbiór zawierający łańcuch pusty {ε}
będący zbiorem regularnym,
(3) 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,
(4) 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:
(a) p|q – wyrażenie regularne oznaczające P ∪ Q – sumę teoriomnogościową
zbiorów P i Q będącą zbiorem regularnym,
(b) pq – wyrażenie regularne oznaczające PQ – złożenie (konkatenację) zbiorów
P i Q będące zbiorem regularnym,
(c) p* - wyrażenie regularne oznaczające P* - domknięcie Kleene’ego zbioru P
będące zbiorem regularnym.
(5) 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:
(1) ( ) - najwyższy,
(2) *
(3) · - (konkatenacja)
(4) | - 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.
... zobacz całą notatkę
Komentarze użytkowników (0)