Star di Kleene
La star di Kleene (o stella di Kleene, o chiusura di Kleene) è un'operazione unaria definita sui linguaggi su un dato alfabeto.
Nozioni introduttive[modifica]
Sia A un insieme che chiameremo alfabeto. Si definisce universo linguistico di A, e si indica con A*, l'insieme formato delle 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]
Se L è un linguaggio, si definisce star di Kleene l'operazione:







