Domknięcie Kleene’ego

Domknięcie Kleene’ego – unarny operator ${\displaystyle *}$ 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 ${\displaystyle V}$ definiuje się rekurencyjnie:

Niech

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

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

Wtedy:

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

gdzie ${\displaystyle \epsilon }$ oznacza słowo puste

Podstawowe własności

• Domknięcie Kleene’ego jest idempotentne:

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

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

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

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

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

• Zachodzi zależność:

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

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

Notacja

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

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

${\displaystyle 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 ${\displaystyle A=\{0,1\},}$ to ${\displaystyle A^{*}}$ jest zbiorem wszystkich ciągów zero-jedynkowych 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

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

Wtedy

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