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: