Domknięcie Kleene’ego

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Domknięcie Kleene'ego)
Przejdź do nawigacji Przejdź do wyszukiwania

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 formalna[edytuj | edytuj kod]

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

Niech

dla

Wtedy:

gdzie oznacza słowo puste

Podstawowe własności[edytuj | edytuj kod]

  • 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

Notacja[edytuj | edytuj kod]

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

Przykłady[edytuj | edytuj kod]

Przykład 1[edytuj | edytuj kod]

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 zerojedynkowych o skończonej długości.

Przykład 2[edytuj | edytuj kod]

^[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 3[edytuj | edytuj kod]

Niech

Wtedy