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 ,
gdzie oznacza słowo puste,
wtedy[1]:
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 wyższy priorytet niż konkatenacja oraz suma.
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
Przypisy
[edytuj | edytuj kod]- ↑ Hopcroft, Motwani i Ullman 2007 ↓, s. 87.
Bibliografia
[edytuj | edytuj kod]- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Wyd. 3. 2007. ISBN 0-321-45536-3.