Domknięcie Kleene'ego

Z Wikipedii

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: pytanie: czy nazwa nie powinna brzmieć domknięcie Kleenego, dodatkowo: co to jest ε (zgaduję, że ciąg pusty)?. Po naprawieniu wszystkich błędów można usunąć tę wiadomość.

Domknięcie Kleene'ego - w logice oraz językach formalnych unarny operator * stosowany do zbiorów zawierających znaki lub napisy. Zapisuje się go postfiksowo (tak jak silnię).

Spis treści 1 Definicja 2 Podstawowe własności 3 Przykłady 3.1 Przykład 1 3.2 Przykład 2 4 Zobacz też

[edytuj] Definicja

Domknięcie Kleene'ego zbioru V definiuje się rekurencyjnie:
Niech

dla .

Wtedy:

[edytuj] Podstawowe własności

• Domknięcie Kleene'ego jest idempotentne:

.

• Każdy zbiór zawiera się w swoim domknięciu Kleen'ego:

.

• Domknięciem Kleene'ego zbioru pustego jest zbiór zawierający słowo puste (a nie zbiór pusty):

• Zachodzi zależność:

.

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

[edytuj] Przykłady

[edytuj] Przykład 1

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.

[edytuj] Przykład 2

Niech

.

Wtedy

[edytuj] Zobacz też

• Wyrażenie regularne (informatyka teoretyczna)