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ę). Oznaczenie to wprowadził amerykański matematyk Stephen Cole Kleene.

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}.

gdzie $\epsilon$ oznacza słowo puste.

Wtedy^[1]:

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

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 wyższy priorytet niż konkatenacja oraz suma.

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

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

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 zero-jedynkowych o skończonej długości.