Domknięcie Kleene’ego
Przejdź do nawigacji
Przejdź do wyszukiwania
Domknięcie Kleene’ego – unarny 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]
- Domknięcie Kleene’ego jest idempotentne:
- 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 zero-jedynkowych 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