Star di Kleene

Da Wikipedia, l'enciclopedia libera.

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 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[modifica | modifica wikitesto]

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:

Definizione[modifica | modifica wikitesto]

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