Star di Kleene

Template:F 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 su 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

Sia $A$ un insieme che chiameremo alfabeto. Si definisce universo linguistico di $A$, e si indica con $A^{*}$, l'insieme formato dalle 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 ,\mathrm{\forall }\alpha \in A^{*}.$

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

$S_x\left(\alpha \right)=\alpha x,\mathrm{\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^{*}=𝒞los(\left\{\epsilon \right\},\{S_x|\mathrm{\forall }x\in A\}).$

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:

$a^n=\underset{n}{\underbrace{aaa\dots a}}.$

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=\{\alpha \beta |\alpha \in L_1,\beta \in L_2\}.$

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,n\in N.$

Definizione

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

$L^{*}=\bigcup _{n\in N}{L}^n.$