Zbiory regularne



Pobieranie 15.93 Kb.
Data28.04.2016
Rozmiar15.93 Kb.
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:

    1. P Q – suma teoriomnogościowa zbiorów P i Q,

    2. PQ – złożenie (konkatenacja) zbiorów P i Q,

    3. 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:

    1. p|q – wyrażenie regularne oznaczające P Q – sumę teoriomnogościową zbiorów P i Q będącą zbiorem regularnym,

    2. pq – wyrażenie regularne oznaczające PQ – złożenie (konkatenację) zbiorów P i Q będące zbiorem regularnym,

    3. p* - wyrażenie regularne oznaczające P* - domknięcie Kleene’ego zbioru P będące zbiorem regularnym.

  1. 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.


©absta.pl 2016
wyślij wiadomość

    Strona główna