Star di Kleene

Da Wikipedia, l'enciclopedia libera.

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

[modifica] 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. Le sequenze di A*, dette anche parole, si indicano giustapponenendo gli elementi di A che le formano. 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 an 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 L1 e L2 due linguaggi su A, possiamo definire la seguente operazione:


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


Inoltre, se L è un linguaggio, definiamo la seguente notazione:


L^0 = \left \{ \lambda \right \}
L^{n+1} = L L_n, n \in N

[modifica] Definizione

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


L^* = \cup_{n \in N} L^n


Estratto da "http://it.wikipedia.org/wiki/Star_di_Kleene"
Strumenti personali