✖

Espressioni regolari

Un’espressione regolare è una stringa di testo che permette di descrivere un insieme di parole. Possiamo vedere le espressioni regolari anche come un modo semplice per descrivere un automa a stati finiti.

Che cos’è un’espressione regolare

In aritmetica usiamo simboli come · e + per costruire un’espressione, per esempio (2 + 3) · 4. Calcolando questa espressione otteniamo un numero. Un’espressione regolare è una sequenza di caratteri e di alcuni simboli speciali, per esempio a(x ∪ y), e il suo valore è un linguaggio (formale). Il risultato dell’espressione (2 + 3) · 4 è il numero 20, il risultato dell’espressione regolare a(x ∪ y) è l’insieme di due parole «ax», «ay».

Come valuteremmo l’espressione regolare a(x ∪ y)? Ogni lettera è in realtà un’abbreviazione dell’insieme formato da quella sola lettera, e la moltiplicazione sottintesa è la concatenazione delle parole. L’espressione regolare si potrebbe quindi riscrivere «per esteso» così:

{a}∘({x}∪{y})

Poi la valuteremmo così: l’unione {x} ∪ {y} ci dà il linguaggio {x,y}. Concatenando i linguaggi {a} e {x,y} otteniamo il linguaggio {ax, ay}.

Le espressioni regolari si usano molto spesso in programmazione e la maggior parte dei linguaggi di programmazione le implementa in qualche modo. Servono, per esempio, a verificare che un testo inserito dall’utente soddisfi certi criteri (ad es. se è un indirizzo e-mail valido, una data valida ecc.) oppure a sostituire parti di testo (ad es. per sostituire tutti gli URL di un testo con collegamenti cliccabili).

Le implementazioni reali delle espressioni regolari sono in genere più potenti di quelle descritte qui e usano una sintassi leggermente diversa, ma soprattutto più complicata.

Definizione di espressione regolare

Definiamo l’espressione regolare su un alfabeto Σ. Diciamo allora che un’espressione regolare è:

  1. a, dove a ∈ Σ. Cioè un singolo simbolo dell’alfabeto è un’espressione regolare.
  2. ϵ: la parola vuota, che in programmazione si scrive anche con due virgolette vuote «».
  3. ∅: un’espressione regolare deve saper descrivere anche il linguaggio vuoto, quindi il linguaggio vuoto è un’espressione regolare.
  4. (R1 ∪ R2), dove R1, R2 sono espressioni regolari.
  5. (R1 ∘ R2), dove R1, R2 sono espressioni regolari.
  6. (R∗), dove R è un’espressione regolare.

Al posto del simbolo ∪ del punto 4 possiamo usare anche la barra verticale: |. Al posto del simbolo ∘ non serve scrivere nulla. Come di solito non scriviamo il simbolo di moltiplicazione, il punto centrato ·, così di solito non scriviamo nemmeno il simbolo di concatenazione ∘. Queste espressioni regolari sono quindi identiche: a ∘ (b ∪ c) e a(b|c).

Che cosa significano i singoli operatori?

  • ∪ oppure | indica l’unione di linguaggi.
  • ∘ indica la concatenazione di linguaggi.
  • ∗ indica la chiusura di Kleene di un linguaggio.

Esempi:

  • a indica il linguaggio semplice {a}.
  • a|b indica il linguaggio formato da due parole {a, b}.
  • a ∘ b indica il linguaggio {ab}.
  • a(b|c)d indica il linguaggio {abd, acd}.
  • a(b∗) indica il linguaggio di tutte le parole che iniziano con la lettera «a», seguita da un numero qualsiasi di lettere «b».
  • (ab)∗ indica il linguaggio di tutte le parole {ϵ, ab, abab, ababab, …}.
  • 0∗10∗ indica il linguaggio di tutte le parole binarie che contengono esattamente un 1. (Osserva che sarebbe più preciso scrivere l’espressione così: (0∗)1(0∗), ma se la scrittura è leggibile anche senza, possiamo omettere le parentesi.)
  • Σ∗1Σ∗ indica il linguaggio di tutte le parole che contengono almeno un 1.
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ indica il linguaggio di tutti i numeri naturali diversi da zero.

Più avanti vedremo l’equivalenza tra le espressioni regolari e gli automi a stati finiti. Per ogni espressione regolare il cui valore è il linguaggio R esiste un automa a stati finiti A tale che L(A) = R, e viceversa.

Fonti

Capitoli: Espressioni regolari, Conversione di un’espressione regolare in automa, Automa a stati finiti non deterministico generalizzato, Conversione di un automa in espressione regolare