Domknięcie Kleene'ego

Domknięcie Kleene'ego - w logice oraz językach formalnych unarny operator $*$ stosowany do zbiorów zawierających znaki lub napisy. Zapisuje się go postfiksowo (tak jak silnię).

Definicja

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

Niech

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

Wtedy

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

Zobacz też

• Wyrażenie regularne (informatyka teoretyczna)