Star di Kleene
Da Wikipedia, l'enciclopedia libera.
La star di Kleene (o stella di Kleene) è una operazione definita sui linguaggi di un dato alfabeto.
[modifica] Nozioni introduttive
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. Le sequenze di A*, dette anche parole, si indicano giustapponenendo gli elementi di A che le formano. 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 an la parola di A* ottenuta giustapponendo n volte a, ossia:
Se indichiamo con L1 e L2 due linguaggi su A, possiamo definire la seguente operazione:
Inoltre, se L è un linguaggio, definiamo la seguente notazione:
[modifica] Definizione
Se L è un linguaggio, si definisce star di Kleene l'operazione:
