Domknięcie Kleene’ego

Z Wikipedii, wolnej encyklopedii

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

gdzie oznacza słowo puste.

Wtedy[1]:

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]

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]

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.