Domknięcie Kleene'ego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Domknięcie Kleene'egounarny operator stosowany do zbiorów zawierających znaki lub napisy. Zapisuje się go postfiksowo (tak jak silnię).

Definicja formalna[edytuj]

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

Niech

dla .

Wtedy:

gdzie oznacza słowo puste

Podstawowe własności[edytuj]

.
  • 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]

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

Przykłady[edytuj]

Przykład 1[edytuj]

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]

^[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]

Niech

.

Wtedy