Apri il menu principale

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 introduttiveModifica

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   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à:

 

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

 

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:

 

Si definisce linguaggio sull'alfabeto A ogni sottoinsieme L di A*. Se  , si indica con   la parola di A* ottenuta giustapponendo   volte  , ossia:

 

Se indichiamo con   e   due linguaggi su A, possiamo definire la seguente operazione di prodotto (o concatenazione) tra linguaggi:

 

Inoltre, se   è un linguaggio, definiamo la seguente nozione di potenza  -esima:

 
 

DefinizioneModifica

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