Star di Kleene

(Reindirizzamento da Stella 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 viene scritta come ; 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   un insieme che chiameremo alfabeto. Si definisce universo linguistico di  , e si indica con  , l'insieme formato dalle sequenze finite di elementi di  . Gli elementi di  , detti anche parole, sono dunque ottenuti concatenando un numero arbitrario (ma finito) di elementi di  , 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  , è solitamente indicata con il simbolo  . Per la parola vuota vale la seguente proprietà:

 

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

 

Si dimostra che   coincide con la chiusura induttiva dell'insieme formato dalla parola vuota   rispetto all'insieme delle operazioni di concatenazione definite su tutti gli elementi di  , ossia:

 

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

 

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

 

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

 
 

DefinizioneModifica

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