Star di Kleene

Questa voce o sezione sugli argomenti teorie dell'informatica e logica non cita le fonti necessarie o quelle presenti sono insufficienti.

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 ${\displaystyle V}$ viene scritta come ${\displaystyle 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

Sia ${\displaystyle A}$ un insieme che chiameremo alfabeto. Si definisce universo linguistico di ${\displaystyle A}$, e si indica con ${\displaystyle A^{*}}$, l'insieme formato dalle sequenze finite di elementi di ${\displaystyle A}$. Gli elementi di ${\displaystyle A^{*}}$, detti anche parole, sono dunque ottenuti concatenando un numero arbitrario (ma finito) di elementi di ${\displaystyle A}$, che prendono il nome di lettere dell'alfabeto. Se ${\displaystyle \alpha }$ e ${\displaystyle \beta }$ sono due parole, indichiamo con ${\displaystyle \alpha \beta }$ la parola ottenuta concatenando le parole date nell'ordine in cui compaiono.

La parola vuota, ossia la sequenza costituita da zero elementi di ${\displaystyle A}$, è solitamente indicata con il simbolo ${\displaystyle \varepsilon }$. Per la parola vuota vale la seguente proprietà:

${\displaystyle \alpha \varepsilon =\varepsilon \alpha =\alpha ,\quad \forall \alpha \in A^{*}.}$

Per ogni elemento ${\displaystyle x}$ di ${\displaystyle A}$, l'operazione di concatenazione si definisce come:

${\displaystyle S_{x}\left(\alpha \right)=\alpha x,\quad \forall \alpha \in A^{*}.}$

Si dimostra che ${\displaystyle A^{*}}$ coincide con la chiusura induttiva dell'insieme formato dalla parola vuota ${\displaystyle \varepsilon }$ rispetto all'insieme delle operazioni di concatenazione definite su tutti gli elementi di ${\displaystyle A}$, ossia:

${\displaystyle A^{*}={\mathcal {C}}los\left(\left\{\varepsilon \right\},\left\{S_{x}\;|\;\forall x\in A\right\}\right).}$

Si definisce linguaggio sull'alfabeto ${\displaystyle A}$ ogni sottoinsieme ${\displaystyle L}$ di ${\displaystyle A^{*}}$. Se ${\displaystyle n\in N,a\in A}$, si indica con ${\displaystyle a^{n}}$ la parola di ${\displaystyle A^{*}}$ ottenuta giustapponendo ${\displaystyle n}$ volte ${\displaystyle a}$, ossia:

${\displaystyle a^{n}=\underbrace {aaa\ldots a} _{n}.}$

Se indichiamo con ${\displaystyle L_{1}}$ e ${\displaystyle L_{2}}$ due linguaggi su ${\displaystyle A}$, possiamo definire la seguente operazione di prodotto (o concatenazione) tra linguaggi:

${\displaystyle L_{1}\cdot L_{2}=\left\{\alpha \beta \;|\;\alpha \in L_{1},\beta \in L_{2}\right\}.}$

Inoltre, se ${\displaystyle L}$ è un linguaggio, definiamo la seguente nozione di potenza ${\displaystyle n}$-esima:

${\displaystyle L^{0}=\left\{\varepsilon \right\},}$

${\displaystyle L^{n+1}=L\cdot L^{n},\quad n\in N.}$

Definizione

Se ${\displaystyle L}$ è un linguaggio, si definisce star di Kleene l'operazione:

${\displaystyle L^{*}=\bigcup _{n\in N}L^{n}.}$

Portale Informatica

Portale Matematica