Utente:LoStrangolatore/Espressioni regolari/Teoria dei linguaggi formali

Espressioni regolari

Uno strumento utile alla definizione di grammatiche regolari definiremo ora le espressioni regolari: una espressione regolare è una stringa di simboli che rappresenta (attraverso l'utilizzo di determinati operatori) tutte le possibili frasi che possono essere generate da una particolare grammatica regolare. Essa sarà dunque una stringa costituita da non terminali appartenenti alla grammatica regolare mescolati ad altri simboli (gli operatori) in modo da rappresentare tutte e solo le possibili frasi generabili dalla grammatica. Le operazioni che si possono compiere sulle espressioni regolari sono simili a quelle che si possono compiere sui linguaggi e sono:

• Unione

Se r_a e r_b sono due espressioni regolari, r_u = r_a | r_b è l'espressione regolare derivante dall'unione dei due linguaggi che le espressioni di partenza rappresentavano. Ad es. r₁ = aa rappresenta il linguaggio L₁ = {aa}, r₂ = bb rappresenta il linguaggio L₂ = {bb} e l'espressione r₃ = r₁ | r₂ = aa | bb rappresenta il linguaggio L₃ = {aa,bb}.

• Concatenazione

Se r_a e r_b sono due espressioni regolari, r_c = r₁r₂ sarà l'espressione che realizza la concatenazione dei due linguaggi rappresentati da r_a e r_b. Con riferimento all'esempio precedente r₄ = r₁r₂ = aabb e rappresenta il linguaggio L₄ = {aabb}.

• Stella di Kleene

Se r_a è un'espressione regolare che rappresenta il linguaggio L, r_a^* rappresenterà il linguaggio L^*. Ad esempio r₅ = a r₅^* = ε|a|aa|aaa|aaaa|... (ε denota il linguaggio vuoto).

r_a⁺ = r_ar_a^*.

Vediamo qualche esempio di espressione regolare:
- a^*b^*c^* denota un linguaggio nel quale le frasi hanno un certo numero di a seguite da un certo numero di b seguite da un certo numero di c. Frasi come abbcc oppure bbcc oppure aaaaa oppure ε appartengono al linguaggio rappresentato dall'espressione regolare mentre frasi come abca oppure bbba non vi appartengono.
- L = {aⁿb^m n≥0,m≥2} L'espressione regolare per questo linguaggio è a^*bbb^*.
- L = {aⁿbⁿ n≥0} Perché l'espressione regolare di questo linguaggio non è a^*b^* ? Perché siamo vincolati dal fatto che l'esponente di a è lo stesso di b! Il linguaggio non può essere espresso utilizzando gli operatori delle espressioni regolari quindi esso non è regolare. Vediamo la grammatica che genera questo linguaggio: T = {a,b} V = {S} S = {S} P = { S→aSb, S→ε } essa non può essere né lineare destra né lineare sinistra (in qualsiasi modo la rigiri) quindi non è una grammatica regolare.
Possiamo dunque enunciare il seguente teorma:
Un linguaggio è regolare se e solo se può essere interamente espresso in termini di unione, concatenazione e stella di Kleene.

Proprietà delle espressioni regolari

Vediamo adesso alcune proprietà degli operatori delle espressioni regolari:
Siano r, s e t delle espressioni regolari.

• Commutativa dell'unione

r|s = s|r

Attenzione perché la concatenazione non è commutativa infatti rs ≠ sr

• Associativa dell'unione

r|(s|t) = (r|s)|t

• Associativa della concatenazione

r(st) = (rs)t

• Distributiva della concatenazione rispetto all'unione

r(s|t) = rs|rt

(s|t)r = sr|tr

• Elemento neutro della concatenazione

εr = rε = r

• Idempotenza della stella di Kleene

r** = r*

• Rapporto tra stella e ε

(r|ε)* = r*

• Altre proprietà

(r*s*)* = (r*|s)* = (r|s*)* = (r|s)*

r*(r|s)* = (r|s)*