Star di Kleene

La star di Kleene (o stella di Kleene, o chiusura di Kleene) è un'operazione unaria definita sui linguaggi su 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 $\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 $\lambda$. 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 $\lambda$ 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^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 \{ \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 Informatica

Portale Matematica