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

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

Wtedy^[1]:

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

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

${\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 \}$

Przypisy

Bibliografia

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Wyd. 3. 2007. ISBN 0-321-45536-3.