Star di Kleene

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

Se A è un insieme, A* è defintito come l'insieme delle sequenze finite di elementi di A; A* viene anche detto universo linguistico di A. Una sequenza di A* si indica giustapponenendo gli elementi di A che la formano. Le sequenze così definite sono dette parole (o stringhe) su A mentre A è detto alfabeto. Gli elementi di A coincidono con le parole di A* costituite da un solo elemento di A. Se ${\displaystyle \alpha }$ e ${\displaystyle \beta }$ sono due parole, indichiamo con ${\displaystyle \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 ${\displaystyle \lambda }$. Per la parola vuota vale la seguente proprietà:

${\displaystyle \alpha \lambda =\lambda \alpha =\alpha ,\forall \alpha \in A^{*}}$

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

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

Si dimostra che A* coincide con la chiusura induttiva dell'insieme formato dalla sola parola vuota rispetto all'operazione di concatenamento, ossia:

${\displaystyle A^{*}={\mathcal {C}}los\left(\left\{\lambda \right\},\left\{S_{x}\forall x\in A\right\}\right)}$

Un linguaggio L su un alfabeto A è un sottoinsieme di A*.