Domknięcie Kleene’ego

Ten artykuł dotyczy matematyki. Zobacz też: inne znaczenia słowa „Domknięcie”.

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 V {\displaystyle V} definiuje się rekurencyjnie; niech

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

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

Wtedy[1]:

V ∗ = ⋃ i = 0 + ∞ V i {\displaystyle V^{*}=\bigcup _{i=0}^{+\infty }V^{i}}

Podstawowe własności

∀ V   V ∗ = ( V ∗ ) ∗ . {\displaystyle \forall V\ V^{*}=(V^{*})^{*}.}
  • Każdy zbiór zawiera się w swoim domknięciu Kleene’ego:
∀ V   V ⊆ V ∗ . {\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ść:
∀ V   ϵ ∈ V ∗ . {\displaystyle \forall V\ \epsilon \in V^{*}.}
  • Dla dowolnego języka regularnego V {\displaystyle V} , język V ∗ {\displaystyle V^{*}} jest regularny.

Notacja

  • Domknięcie Kleene’ego ma wyższy priorytet niż konkatenacja oraz suma.
A = { a }     B = { b }     C = { c } {\displaystyle A=\{a\}\ \ B=\{b\}\ \ C=\{c\}}
A ∪ B C ∗ = { a , b , b c , b c c , b c 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 A = { 0 , 1 } , {\displaystyle A=\{0,1\},} to A ∗ {\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

V = { b a , c a } . {\displaystyle V=\{ba,ca\}.}

Wtedy

V ∗ = { ϵ , b a , c a , b a b a , b a c a , c a c a , c a b a , b a b a c a , … } {\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.