La chiusura di Kleene di un linguaggio

La chiusura di Kleene di un linguaggio A, indicata con A^∗, è l'insieme di tutte le possibili stringhe che si possono formare concatenando zero o più volte le stringhe di A. $$ A^* =  \bigcup_{i=0}^{\infty} A^i $$

In pratica, è come se potessi scrivere qualsiasi numero di stringhe da A, una dopo l'altra, inclusa la possibilità di non scrivere nulla che corrisponde a A⁰.

Esempio

Immagina di avere un alfabeto semplice \( A = \{a, b\} \).

La chiusura di Kleene di \( A \), che indichiamo con \( A^* \), includerà tutte le stringhe possibili che possono essere create usando le lettere 'a' e 'b' in qualsiasi quantità, inclusa la stringa vuota.

Ecco alcuni esempi di stringhe che fanno parte della chiusura di Kleene di \( A \):

1. \( \lambda \) (la stringa vuota)
2. a
3. b
4. aa
5. bb
6. ab
7. ba
8. aba
9. bab
10. aab
11. bba
12. aaa
13. bbb
14. .. e così via, all'infinito.

Qualsiasi combinazione di 'a' e 'b', di qualsiasi lunghezza, è inclusa in \( A^* \).

Dal momento che qualsiasi numero include anche lo zero come possibilità, la stringa vuota $ \lamda $ è sempre un membro di $ A^∗ $ indipendentemente da cosa sia A.

La chiusura di Kleene è molto potente perché crea un insieme infinito a partire da un insieme finito di simboli.