Zbiory regularne

Zbiory regularne

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.
   

Niech T = {a, b}. Zbiorem regularnym nad T jest np. zbiór:

{, a, ab, abb, abbb, abbbb, ...} = {}  {a}{b}^*

Wyrażenia regularne

Niech T będzie alfabetem.

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.
   

5. 
   nic innego poza tym, co wynika z punktów (1) – (4), nie jest wyrażeniem regularnym.
   

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.
   

Przykład:

bo:

= {a, ab, abb, ...} = {a}{b}^*