Star di Kleene: differenze tra le versioni

Versione delle 18:58, 14 dic 2004

Versione attuale delle 21:48, 9 nov 2023

(66 versioni intermedie di 43 utenti non mostrate)

Riga 1:

{{F|teorie dell'informatica|arg2=logica|marzo 2013}}

La '''[[star di Kleene]]''' (o '''stella di Kleene''') è una operazione definita sui linguaggi di un dato [[alfabeto]].

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 <math>V</math> viene scritta come <math>V^*</math>; viene impiegata normalmente nelle [[espressioni regolari]], contesto in cui [[Stephen Kleene]] ha introdotto originariamente tale concetto, stante ad indicare "zero o più".

== Nozioni introduttive ==

Se A è un [[insieme]], '''A*''' è defintito come l'insieme delle sequenze finite di elementi di A; A* viene anche detto '''universo linguistico''' di A. Una sequenza di A* si indica giustapponenendo gli elementi di A che la formano. Le sequenze così definite sono dette '''[[parola|parole]]''' (o [[stringa|stringhe]]) su A mentre A è detto '''[[alfabeto]]'''. Gli elementi di A coincidono con le parole di A* costituite da un solo elemento di A.

Sia <math>A</math> un [[insieme]] che chiameremo [[Alfabeto (teoria dei linguaggi formali)|alfabeto]]. Si definisce universo linguistico di <math>A</math>, e si indica con <math>A^*</math>, l'insieme formato dalle sequenze finite di elementi di <math>A</math>. Gli elementi di <math>A^*</math>, detti anche [[Parola|parole]], sono dunque ottenuti concatenando un numero arbitrario (ma finito) di elementi di <math>A</math>, che prendono il nome di lettere dell'alfabeto. Se <math>\alpha</math> e <math>\beta</math> sono due parole, indichiamo con <math>\alpha \beta</math> la parola ottenuta concatenando le parole date nell'ordine in cui compaiono.

La '''parola vuota''', ossia la sequenza costituita da zero elementi di <math>A</math>, è solitamente indicata con il simbolo <math>\lambdavarepsilon</math>. Per la parola vuota vale la seguente proprietà:

:<math>\alpha \lambdavarepsilon = \lambdavarepsilon \alpha = \alpha, \quad\forall \alpha \in A^*.</math>

Per ogni elemento <math>x</math> appartenente addi <math>A</math>, si definisce l'[[operazione]] di '''concatenazione''' si definisce come:

<math>\alpha \lambda = \lambda \alpha = \alpha, \forall \alpha \in A^*</math>

:<math>S_x \left ( \alpha \right ) = \alpha x,\quad \forall \alpha \in A^*.</math>

Si dimostra che <math>A^*</math> coincide con la [[chiusura induttiva]] dell'insieme formato dalla parola vuota <math>\varepsilon</math> rispetto all'insieme delle operazioni di concatenazione definite su tutti gli elementi di <math>A</math>, ossia:

Per ogni elemento x appartenente ad A, si definisce l'[[operazione]] di '''concatenazione''' come:

:<math>A^* = \mathcal{C} los \left ( \left \{ \lambdavarepsilon \right \}, \left \{ S_x \;|\; \forall x \in A \right \} \right ).</math>

Si definisce linguaggio sull'alfabeto <math>A</math> ogni [[sottoinsieme]] <math>L</math> di <math>A^*</math>. Se <math>n \in N, a \in A</math>, si indica con <math>a^n</math> la [[parola]] di <math>A^*</math> ottenuta giustapponendo <math>n</math> volte <math>a</math>, ossia:

<math>S_x \left ( \alpha \right ) = \alpha x, \forall \alpha \in A^*</math>

:<math>a^n =\underbrace{aaa \ldots a}_n.</math>

Se indichiamo con <math>L_1</math> e <math>L_2</math> due linguaggi su <math>A</math>, possiamo definire la seguente operazione di prodotto (o concatenazione) tra linguaggi:

Si dimostra inoltre che:

:<math>L_1 \cdot L_2 = \left \{ \alpha \beta \;|\; \alpha \in L_1, \beta \in L_2 \right \}.</math>

Inoltre, se <math>L</math> è un linguaggio, definiamo la seguente nozione di potenza <math>n</math>-esima:

<math>A^* = \mathcal{C} los \left ( \left \{ \lambda \right \}, \left \{ \right \} \right )</math>

:<math>L^0 = \left \{ \varepsilon \right \},</math>

:<math>L^{n+1} = L \cdot L^{n},\quad n \in N.</math>

==Definizione==

Un '''linguaggio''' L su un alfabeto A è un sottoinsieme di A*.

Se <math>L</math> è un linguaggio, si definisce star di Kleene l'operazione:

:<math>L^* = \bigcup_{n \in N} L^n.</math>

{{Portale|informatica|matematica}}

[[Categoria:Matematica per l'informatica]]

[[Categoria:Teoria dei linguaggi formali]]

[[Categoria:Teoria degli insiemi]]