Domknięcie Kleene’ego

Domknięcie Kleene’ego – unarny operator $*$ stosowany do zbiorów zawierających znaki lub napisy. Zapisuje się go postfiksowo (tak jak silnię).

Definicja formalna

Domknięcie Kleene’ego zbioru $V$ definiuje się rekurencyjnie:

Niech

$V^{0}=\{\epsilon \}$

$V^{i+1}=\{wv:w\in V^{i}\wedge v\in V\}$ dla $i\in \mathbb {N} _{0}$.

Wtedy:

$V^{*}=\bigcup _{i=0}^{+\infty }V^{i}$

gdzie $\epsilon$ oznacza słowo puste

Podstawowe własności

• Domknięcie Kleene’ego jest idempotentne:

$\forall V~V^{*}=(V^{*})^{*}$.

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

$\forall V~V\subseteq V^{*}$.

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

$\varnothing ^{*}=\{\epsilon \}$

• Zachodzi zależność:

$\forall V~\epsilon \in V^{*}$.

• Dla dowolnego języka regularnego $V$, język $V^{*}$ jest regularny

Notacja

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

$A=\{a\}~~B=\{b\}~~C=\{c\}$

$A\cup BC^{*}=\{a,b,bc,bcc,bccc,...\}$

Przykłady

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 $A=\{0,1\}$, to $A^{*}$ jest zbiorem wszystkich ciągów zerojedynkowych o skończonej długości.

Przykład 2

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

Niech

$V=\{ba,ca\}$.

Wtedy

$V^{*}=\{\epsilon ,ba,ca,baba,baca,caca,caba,babaca,...\}$