Domknięcie Kleene’ego

Szablon:Inne znaczenia 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=\{ϵ\}$

$V^{i+1}=\{wv:w\in V^i\wedge v\in V\}$ dla $i\in {\mathbb{N}}_0$,

gdzie $ϵ$ oznacza słowo puste,

wtedySzablon:Odn:

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

Podstawowe własności

• Domknięcie Kleene’ego jest idempotentne:

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

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

$\mathrm{\forall }VV\subseteq V^{*}.$

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

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

• Zachodzi zależność:

$\mathrm{\forall }Vϵ\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 B{C}^{*}=\{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.

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^{*}=\{ϵ,ba,ca,baba,baca,caca,caba,babaca,\dots \}$

Bibliografia

• Szablon:Cytuj książkę