Linguaggi ed espressioni regolari

lezione Linguaggi ed espressioni regolari
	Tipo: lezione
	Materia: Linguaggi formali e automi
	Avanzamento: lezione completa al 100%

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}$ $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}$ $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}$ $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

«Un insieme è chiuso rispetto a un'operazione se e solo se ogni insieme ottenuto applicando l'operazione ai membri dell'insieme originale, l'insieme ottenuto è contenuto nell'insieme originario»

${\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/

Altri progetti

Wikibooks contiene testi o manuali sulle espressioni regolari
Wikipedia contiene informazioni sulle espressioni regolari
Wikimedia Commons contiene immagini o altri file sulle espressioni regolari