Espressioni regolari

todo

Usate per specificare pattern di ricerca nei word-processors.

Nella quasi totalità dei casi, le espressioni regolari utilizzate sono le espressioni regolari estese, che sono la versione più corta da scrivere delle espressioni regolari base.

Espressioni regolari pure

Una espressione regolare su un alfabeto $\sum$ rappresenta un insieme di stringhe (linguaggio) composte da quell’alfabeto.

Avendo $\sum =\{0,1\}$ la definizione è:

• se $x\in \sum$, $x$ è una espressione regolareche rappresenta il linguaggio $\{x\}$
• $\text{espilon}$ è la stringa vuota, ed è anche una espressione regolare che rappresenta il linguaggio $\{ϵ\}$ composto dalla sola stringa vuota

espressioni regolari elementari: espressioni che formano la base della costruzione ricorsiva

Composizione

Le espressioni regolari hanno tre regole di composizione e concatenazione. Con $E$ ed $F$ espressioni regolari che denotano rispettivamente $L_E$ e $L_F$, si ha

1. $EF$ è espressione regolare che denota $L_{EF}=z:z=xy,x\in L_E,y\in L_F$ Questo esprime la concatenazione dei linguaggi, e si può rappresentare con $L_{EF}=L_E{L}_F$. 00 è la concatenazione di due espressioni elementari. Il linguaggio corrispondente è $\{00\}$
2. $E|F$ è espressione regolare che denota $L_{E|F}=z:z\in L_E\text{ oppure }z\in L_F$Esprime l’unione dei linguaggi, e si può rappresentare con $L_{E|F}=L_E\cup L_F$. 0|1 è l’unione di due espressioni elementari. Il linguaggio corrispondente è $\{0,1\}$

La concatenazione prevale sulla unione a livello di operazione, quindi $00|01$ equivale a $(00)|(01)$, e non $0(0|0)1$.

Essendo associative, $00|01|1$ equivale a $(00|01)|1$.

title: Esempio
$(0|11)(01|10)$ denota il linguaggio: $$\{001, 010, 1101, 1110\}$$

arch1