Star di Kleene

La star di Kleene (o stella di Kleene, o chiusura di Kleene) è una operazione definita sui linguaggi di un dato alfabeto.

Nozioni introduttive

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 α e β sono due parole, indichiamo con αβ 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 λ. Per la parola vuota vale la seguente proprietà:

$\alpha \lambda = \lambda \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 λ rispetto all'insieme delle operazioni di concatenazione definite su tutti gli elementi di A, ossia:

$A^* = \mathcal{C} los \left ( \left \{ \lambda \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ⁿ 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₁ e L₂ 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 \{ \lambda \right \}$

$L^{n+1} = L \cdot L_n,\,\quad n \in N$

Definizione

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

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica