Star di Kleene

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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

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:

Definizione[modifica | modifica wikitesto]

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