Star di Kleene

Da Wikipedia, l'enciclopedia libera.

In logica matematica e in Informatica, la stella di Kleene (o chiusura di Kleene, o operatore di Kleene) è un'operazione unaria definita su un insieme di stringhe o un insieme di simboli o caratteri. In matematica, è più noto come la costruzione di un monoide libero. L'applicazione della stella di Kleene ad un insieme V viene scritta come V*; viene impiegata normalmente nelle espressioni regolari, contesto in cui Stephen Kleene ha introdotto originariamente tale concetto, stante ad indicare "zero o più".

Nozioni introduttive[modifica | modifica sorgente]

Sia A un insieme che chiameremo alfabeto. Si definisce universo linguistico di A, e si indica con A*, l'insieme formato delle sequenze finite di elementi di A. Gli elementi di A*, detti anche parole, sono dunque ottenuti concatenando un numero arbitrario (ma finito) di elementi di A, che prendono il nome di lettere dell'alfabeto. Se \alpha e \beta sono due parole, indichiamo con \alpha \beta la parola ottenuta concatenando le parole date nell'ordine in cui compaiono.

La parola vuota, ossia la sequenza costituita da zero elementi di A, è solitamente indicata con il simbolo \epsilon. Per la parola vuota vale la seguente proprietà:

\alpha \epsilon = \epsilon \alpha = \alpha, \forall \alpha \in A^*

Per ogni elemento x di A, l'operazione di concatenazione si definisce come:

S_x \left ( \alpha \right ) = \alpha x, \forall \alpha \in A^*

Si dimostra che A* coincide con la chiusura induttiva dell'insieme formato dalla parola vuota \epsilon rispetto all'insieme delle operazioni di concatenazione definite su tutti gli elementi di A, ossia:

A^* = \mathcal{C} los \left ( \left \{ \epsilon \right \}, \left \{ S_x \;|\; \forall x \in A  \right \} \right )

Si definisce linguaggio sull'alfabeto A ogni sottoinsieme L di A*. Se n \in N, a \in A, si indica con a^n la parola di A* ottenuta giustapponendo n volte a, ossia:

\begin{matrix}a^n =& \underbrace{a\;a\;a\;...\;a}\\ \; & n \end{matrix}

Se indichiamo con L_1 e L_2 due linguaggi su A, possiamo definire la seguente operazione di prodotto (o concatenazione) tra linguaggi:

L_1 \cdot L_2 = \left \{ \alpha \beta \;|\; \alpha \in L_1, \beta \in L_2 \right \}

Inoltre, se L è un linguaggio, definiamo la seguente nozione di potenza n-esima:

L^0 = \left \{ \epsilon \right \}
L^{n+1} = L \cdot L^{n},\,\quad n \in N

Definizione[modifica | modifica sorgente]

Se L è un linguaggio, si definisce star di Kleene l'operazione:

L^* = \bigcup_{n \in N} L^n.