Espressioni regolari

Una regex (o regular expression) è una notazione che descrive linguaggi regolari per cui, dato un alfabeto $\Sigma$:

• Se $a\in \Sigma$, allora $a$ è una regex
• $ϵ$ è sempre una regex
• $\varnothing$ è anch'esso una regex
• Se $r_1$ e $r_2$ sono regex, allora $r_1\cup r_2$ è una regex
• Se $r_1$ e $r_2$ sono regex, allora $r_1\circ r_2$ è una regex
• Se $r$ è regex, allora $r^{\ast }$ è una regex

dove ${}^{\ast }$, $\circ$ e $\cup$ è l'ordine di rispettiva precedenza, e per convenzione $r_1{r}_2=r_1\circ r_2$.

Il linguaggio $L(R)$ di una regex $R$ invece, è definito come:

1. Se $R=a$ allora $L(R)=\{a\}$
2. Se $R=ϵ$ allora $L(R)=\{ϵ\}$
3. Se $R=\varnothing$ allora $L(R)=\varnothing$
4. Se $R=R_1\cup R_2$ allora $L(R)=L(R_1)\cup L(R_2)$
5. Se $R=R_1\circ R_2$ allora $L(R)=L(R_1)\circ L(R_2)$
6. Se $R={R_1}^{\ast }$ allora $L(R)=L(R_1{)}^{\ast }$

Per esempio, il linguaggio della regex $(0\cup 1)0^{\ast }$ è: $$\begin{array}{rl}L((0\cup 1)0^{\ast })& \underset{5}{=}L(0\cup 1)\circ L(0^{\ast })=\\ & \underset{4,6}{=}(L(0)\cup L(1))\circ L(0{)}^{\ast }=\\ & \underset{1}{=}(\{0\}\cup \{1\})\circ \{0{\}}^{\ast }=\{0,1\}\circ \{0{\}}^{\ast }\end{array}$$