Domknięcie Kleene’ego

Ten artykuł dotyczy matematyki. Zobacz też: inne znaczenia słowa „Domknięcie”.

Domknięcie Kleene’egounarny operator stosowany do zbiorów zawierających znaki lub napisy. Zapisuje się go postfiksowo (tak jak silnię). Oznaczenie to wprowadził amerykański matematyk Stephen Cole Kleene.

Definicja formalnaEdytuj

Domknięcie Kleene’ego zbioru   definiuje się rekurencyjnie:

Niech

 
  dla  

Wtedy:

 

gdzie   oznacza słowo puste

Podstawowe własnościEdytuj

 
  • Każdy zbiór zawiera się w swoim domknięciu Kleene’ego:
 
  • Domknięciem Kleene’ego zbioru pustego jest zbiór zawierający słowo puste (a nie zbiór pusty):
 
  • Zachodzi zależność:
 
  • Dla dowolnego języka regularnego   język   jest regularny

NotacjaEdytuj

  • Domknięcie Kleene’ego ma najwyższy priorytet względem 2 pozostałych podstawowych operacji: konkatenacji oraz sumy
 
 

PrzykładyEdytuj

Przykład 1Edytuj

Domknięciem Kleene’ego dowolnego alfabetu jest język złożony ze wszystkich słów nad tym alfabetem. Przykładowo jeśli   to   jest zbiorem wszystkich ciągów zero-jedynkowych o skończonej długości.

Przykład 2Edytuj

^[01]*$ jest przykładem wyrażenia regularnego (zapis praktyczny) pasującego do każdego elementu domknięcia Kleene’ego dla przykładu 1.

Przykład 3Edytuj

Niech

 

Wtedy