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.
Wyszukiwarka
Podobne podstrony:
lower,urządzenia obiektowe automatyki,zbiorylower,urządzenia obiektowe automatyki,Moorelower,urządzenia obiektowe automatyki,drzewa rozbiorulower,urządzenia obiektowe automatyki,gramatykilower,urządzenia obiektowe automatyki,Turinglower,urządzenia obiektowe automatyki,algorytmy parsingulower,urządzenia obiektowe automatyki,Przeksztalcenia automatówlower,urządzenia obiektowe automatyki,jezyki1d urządzenia obiektowe automatykiszafran,podstawy automatyki, rodzaje regulacjiAutomatyczny układ regulacji odstępu od poprzednika (ACC)motoiler urzadzenie do automatycznego oliwienia lancuchow motorowerow i motocykliUk? regulacji automatycznejWykonywanie połączeń w urządzeniach precyzyjnych i układach automatyki przemysłowejUSM Automatyka w IS (wyklad 3) regulatory ppt [tryb zgodnosci]10 Automatyka i regulacja automatyczna testmechanik automatyki przemyslowej i urzadzen precyzyjnych1a Zadania i metody automatycznej regulacjiwięcej podobnych podstron