Le espressioni regolari

Tranquilli, non vi aspetta un pistolotto moralistico su cosa è lecito e cosa è non è lecito dire. In questi giorni sono impegnato nel progetto “RiStudiamoConVoi“, di assistenza allo studio per studenti del liceo, e la domanda più frequente è “a cosa serve l’algebra” ?

E’ una domanda interessante perché alla base c’è l’idea che di algebra ce ne sia una sola, quella di somme, prodotti, potenze di numeri e tutte le regole che ben conosciamo. Da qui l’idea di raccontare su LidiMatematici un tipo diverso di algebra,  le espressioni regolari.

Immaginiamo di avere a disposizione un insieme di simboli a nostra scelta, ad esempio:

A = {a, b, c}

lo chiameremo alfabeto.

L’idea è di costruire un modello formale che ci consenta di generare sequenze di questi simboli, come ad esempio “aaa” oppure “aabb” o ancora, “acac“. Le sequenze di simboli sono dette stringhe. Per fare ciò, abbiamo bisogno di definire un insieme di operazioni ammesse, in modo tale da costruire stringhe a partire dai singoli simboli dell’insieme A dell’alfabeto. Queste operazioni saranno anch’esse rappresentate da simboli. Simboli speciali, però, perché indicano azioni. I simboli delle operazioni ammesse, che chiameremo operatori, sono quindi diversi dai simboli degli elementi dell’alfabeto.

E’ una distinzione importante, perché il nostro processo di costruzione non ha alcun vincolo, siamo perfettamente liberi di inventare i simboli e di attribuirli ai vari operatori o elementi dell’alfabeto. E’ una nostra scelta.

Vediamo un po’ … la prima operazione che vogliamo è sicuramente di poter scrivere serie di simboli, la chiameremo concatenazione, e la indichiamo con un punto ‘.’:

a.a = aa

decidiamo anche che, per comodità, questo operatore può essere omesso, in modo da rendere più leggibile l’operazione.

La seconda operazione che vogliamo è la possibilità di scegliere alternativamente un simbolo oppure l’altro, chiameremo questo operatore unione, e lo indicheremo con il +. Quindi, ad esempio, usando concatenazione ed unione otteniamo:

a(a+b) = aa oppure ab

Infine, definiamo un terzo operatore che consente di concatenare zero o più  volte, a nostra scelta, una stringa, lo indichiamo con *:

a* = aaaaaaaa …

E’ un operatore molto particolare, che va sotto il nome di Stella di Kleene.

Manca ancora un elemento importantissimo, la stringa vuota, che di norma viene indicata con la lettera greca ε (epsilon). La stella di Kleene ammette infatti anche nessuna ripetizione del simbolo, quindi la stringa vuota ε  è un  risultato ammesso dell’espressione a*.

a*ε, a, aa, aaa, …

Soffermiamoci per ora a giocare con le espressioni regolari, per costruire insiemi di stringhe a partire dai simboli dell’alfabeto e gli operatori che abbiamo definito.

Ad esempio, l’espressione regolare:

a(b+c)b*

ammette come soluzione questo insieme di stringhe:

{ab, ac, abb, abbb…., acb, acbbb …}

Le espressioni regolari sono una vera e propria algebra, detta Algebra di Kleene, e rappresentano un avanzamento dell’umanità. E’ grazie al matematico americano Stephen Kleene se, oggi, abbiamo gli strumenti matematici che ci consentono di  comunicare con i calcolatori elettronici attraverso strutture di linguaggio specifiche, dette linguaggi formali. Per darvi una idea di quanto sia importante il lavoro di Kleene, senza le espressioni regolari internet non sarebbe mai esistita.

Il lavoro di Kleene ha impatti notevoli sullo sviluppo della scienza del calcolatore e correlazioni con altri argomenti fondamentali che abbiamo già esplorato, cioé la teoria della ricorsione, gli automi a stati finiti  e la linguistica computazionale.

Esploreremo presto le relazioni tra tutti questi concetti. A Mercoledì prossimo !

 

Share
Questa voce è stata pubblicata in Teoria e Pratica e contrassegnata con , , , , , , , , . Contrassegna il permalink.

5 risposte a Le espressioni regolari

  1. Annalisa Purpura scrive:

    Questo post mi fa pensare alle ore passate a studiare informatica teorica…. santo De Luca

  2. Terenzio scrive:

    Dopo 10 anni finalmente cercherò di venire a patti con la matematica, e con l’algebra in particolare. Gliel’ho giurato all’esame di stato, che non era finita lì. Bellissimo blog, “istigazione alla conoscenza”, detto bene!

    • LidiMatematici scrive:

      Grazie ! Feedback preziosissimo ….

      • Terenzio scrive:

        Grazie a te! Davvero, mi sa che il mio problema era principalmente con un approccio didattico sbagliato che mi ha lasciato con una “tara psicologica” per la matematica. Ma la sfida deve per forza continuare…

  3. Pingback: Automi a stati finiti ed espressioni regolari | LidiMatematici

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *