Domknięcie Kleene'ego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

\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^*.

Notacja[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

Przykład 1[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Niech

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

Wtedy

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

Zobacz też[edytuj | edytuj kod]