Star di Kleene

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 $\varepsilon$. Per la parola vuota vale la seguente proprietà:

$\alpha \varepsilon =\varepsilon \alpha =\alpha ,\quad \forall \alpha \in A^{*}.$

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

$S_{x}\left(\alpha \right)=\alpha x,\quad \forall \alpha \in A^{*}.$

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

$A^{*}={\mathcal {C}}los\left(\left\{\varepsilon \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:

$a^{n}=\underbrace {aaa\ldots a} _{n}.$

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\{\varepsilon \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}.$