# Linguaggi ed espressioni regolari

In questa lezione analizzeremo la famiglia delle espressioni regolari (in inglese regular expression o, in forma abbreviata, regexp, regex o RE) di cui si invita a leggere come introduzione la relativa pagina di Wikipedia.

## Definizione

Formalmente definiamo espressione regolare una stringa $r$ costruita su un alfabeto $\Sigma =\{a_{1},a_{2},...,a_{k}\}$ e in unione ai seguenti metasimboli:
* $\varnothing$: insieme vuoto
* $\cup$: unione (notazione alternativa: $|$)
* $\cdot$: concatenazione
* $*$: star
* $$: parentesi
Una RE è detta ben formata se si presenta in una delle seguenti forme:
* $r=\varnothing$
* $r=a,\ a\in \Sigma$
* $r=(s\cup t)$ o $r=(s|t)$
* $r=(s\cdot t)$ o $r=(st)$ (notazione alternativa)
* $r=(s)$
dove $s$ e $t$ sono a loro volta espressioni regolari. Si noti che la precedenza degli operatori è:
* $\cdot$
* $\cup$
Definiamo inoltre altri operatori non essenziali ma frequentemente usati, utilizzando solo le proprietà sopra descritte:
* $\varepsilon =\varnothing ^{*}$
* $r^{+}=r\cdot r^{*}$
* $r^{h}=\underbrace {rr...r} _{m}$ (potenza)
* $[r]_{k}^{n}=r^{k}\cup r^{k+1}\cup ...\cup r^{n}$ con $n\geq k$ (ripetizione)
* $[r]=\varepsilon \cup r$
* $(0...9)=0123456789,(a...m)=abcdefghijklm$ (intervalli ordinati)
Altri operatori possono essere quelli insiemistici teorici: intersezione, differenza e complemento. Una espressione regolare che contiene questi operatori è detta espressione regolare estesa. Nota: Il potere espressivo di una RE estesa non è maggiore di quello di una RE standard.

### Definizione di linguaggio regolare

Diciamo che un linguaggio è un linguaggio regolare se è denotato da una RE. Formalmente, un linguaggio regolare $L_{r}$ è un linguaggio su un alfabeto $\Sigma$ che ha una corrispondente RE in accordo con la seguente tabella:
| Espressione | Linguaggio |
| $r=\varepsilon$ | $L_{r}=\{\varepsilon \}$ |
| $r=a\in \Sigma$ | $L_{r}=\{a\}$ |
| $r=s\cup t$ $r=s|t$ | $L_{r}=L_{s}\cup L_{t}$ |
| $r=s\cdot t$ $r=st$ | $L_{r}=L_{s}\cdot L_{t}$ |
| $r=s^{*}$ | $L_{r}=L_{s}^{*}$ |
Denotiamo con ${\textbf {REG}}$ la famiglia di tutti linguaggi regolari e con ${\textbf {FIN}}$ la famiglia di tutti i linguaggi finiti (cioè con cardinalità finita).
Allora possiamo dire che:
    ${\textbf {FIN}}\subset {\textbf {REG}}$
(intuibile: un linguaggio finito può sempre essere visto come l'unione di un numero finito di stringhe, ognuna delle quali concatenazione di un numero finito di simboli dell'alfabeto)

## Derivare il linguaggio dalla RE

Per derivare il linguaggio dobbiamo definire alcuni concetti supplementari.

### Sottoespressione

Definiamo sottoespressione (in inglese subexpression o SE) una ben parentizzata sottostringa di una RE che si presenta nelle parentesi più esterne.
Chiariamo con un esempio. Sia data la RE:
$r=(s\cup (t\cdot (u\cup z)^{+}))$
questa RE ha due SE: $s$ e $(t\cdot (u\cup z)^{+})$, mentre $t$ e $(u\cup z)^{+}$ NON sono SE di $r$, ma sono SE di $(t\cdot (u\cup z)^{+})$.

### Versione numerata

Definiamo 'versione numerata di una RE, la RE a cui vengono aggiunti i numeri alle lettere che compongono la RE, in modo da differenziale le lettere uguali. Anche qui chiariamo il concetto con un esempio:
    $(aa)^{*}\cup (b\cdot ((cc)^{+}\cdot a))$
la sua versione numerata è:
    $(a_{1}a_{2})^{*}\cup (b_{1}\cdot ((c_{1}c_{2})^{+}\cdot a_{3}))$
Questa notazione è importante per definire l'ambiguità di un linguaggio (introdotta nelle sezioni successive).

### Scelta e derivazione

Diciamo che una RE è una scelta (in inglese choice) di un'altra RE nei seguenti casi:
* $e_{k},\ 1\leq k\leq m$ è una scelta di $(e_{1}\cup e_{2}\cup ...\cup e_{k})$
* $e_{m}=\underbrace {e...e} _{m},\ m\geq 1$ è una scelta di $e^{+}$ e $e^{*}$
* $\varepsilon$ è una scelta di $e^{*}$
Diciamo che una SE $e'$ deriva da $e''$ (scritto come $e'\Rightarrow e''$ se:
* $e''$ è una scelta di $e'$;
* oppure, $e''_{i}$ è una scelta di $e'_{i}$ per ogni $1\leq i\leq m$
La derivazione può avvenire più volte allo stesso modo. In questo caso scriviamo:
* $e_{0}{\overset {n}{\Rightarrow }}e_{n}$
** se $e_{0}\Rightarrow e_{1}$, $e_{1}\Rightarrow e_{2}$, ..., $e_{n-1}\Rightarrow e_{n}$ con $n$ fisato
* $e_{0}{\overset {+}{\Rightarrow }}e_{n}$
** se $e_{0}\Rightarrow e_{1}$, $e_{1}\Rightarrow e_{2}$, ..., $e_{n-1}\Rightarrow e_{n}$ con $n\geq 1$
* $e_{0}{\overset {*}{\Rightarrow }}e_{n}$
** se $e_{0}\Rightarrow e_{1}$, $e_{1}\Rightarrow e_{2}$, ..., $e_{n-1}\Rightarrow e_{n}$ con $n\geq 0$

#### Esempi

* $a^{*}\cup b^{+}\Rightarrow a^{*}$
* $a^{*}\cup b^{+}\Rightarrow a^{+}$
* $a^{*}\cup b^{+}\Rightarrow a^{*}\Rightarrow \varepsilon$ o equivalentemente $a^{*}\cup b^{+}{\overset {2}{\Rightarrow }}\varepsilon$ o ancora $a^{*}\cup b^{+}{\overset {+}{\Rightarrow }}\varepsilon$
* $a^{*}\cup b^{+}\Rightarrow b^{+}$
* $a^{*}\cup b^{+}\Rightarrow b^{+}\Rightarrow bbbb$ o equivalentemente $a^{*}\cup b^{+}{\overset {2}{\Rightarrow }}bbbb$ o ancora $a^{*}\cup b^{+}{\overset {+}{\Rightarrow }}bbbb$

### Linguaggio definito da un RE

Il linguaggio definito da una espressione regolare $r$ è:
    $L_{r}=\{x\in \Sigma ^{*}|r{\overset {*}{\Rightarrow }}x\}$
Diciamo che due RE sono equivalenti se definiscono lo stesso linguaggio.

## Ambiguità delle RE

Una stringa di un linguaggio regolare può essere derivato dalla RE in modi differenti, cioè attraverso distinte derivazioni. Diciamo che una RE è ambigua se esiste una stringa derivabile attraverso due distinte derivazioni che non differiscono solo dall'ordine di applicazione.
Esempio:
    $a*\cup (b*\cup a)$
Ambigua, due modi di derivazione di $a$:
* $a*\cup (b*\cup a)\Rightarrow a*\Rightarrow a$
* $a*\cup (b*\cup a)\Rightarrow (b*\cup a)\Rightarrow a$
Condizione sufficiente affinché una RE sia ambigua, se il linguaggio generato dalla RE in versione numerata include due stringhe che coincidono a meno dei numeri.
Esempio:
    $a_{1}*\cup (b_{1}*+\cup a_{2})$
Genera:
* $\varepsilon$
* $a_{1}$
* $a_{1}a_{1}$
* $a_{1}a_{1}a_{1}$
* $b_{1}$
* $b_{1}b_{1}$
* $a_{2}$
Come si vede eliminando i numeri, la stringa 2 coincide con la stringa 7, perciò la RE è ambigua.

## Proprietà di chiusura

${\textbf {REG}}$ è chiuso rispetto alla concatenazione, unione e star (quindi anche per gli altri operatori sopra descritti).

## Link e riferimenti

Esempi pratici - https://www.evemilano.com/come-funzionano-le-espressioni-regolari-regex/