Utente:LoStrangolatore/Espressioni regolari/Teoria dei linguaggi formali

Wikibooks, manuali e libri di testo liberi.
Jump to navigation Jump to search

Espressioni regolari[modifica]

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 ra e rb sono due espressioni regolari, ru = ra | rb è l'espressione regolare derivante dall'unione dei due linguaggi che le espressioni di partenza rappresentavano. Ad es. r1 = aa rappresenta il linguaggio L1 = {aa}, r2 = bb rappresenta il linguaggio L2 = {bb} e l'espressione r3 = r1 | r2 = aa | bb rappresenta il linguaggio L3 = {aa,bb}.
  • Concatenazione
Se ra e rb sono due espressioni regolari, rc = r1r2 sarà l'espressione che realizza la concatenazione dei due linguaggi rappresentati da ra e rb. Con riferimento all'esempio precedente r4 = r1r2 = aabb e rappresenta il linguaggio L4 = {aabb}.
  • Stella di Kleene
Se ra è un'espressione regolare che rappresenta il linguaggio L, ra* rappresenterà il linguaggio L*. Ad esempio r5 = a r5* = ε|a|aa|aaa|aaaa|... (ε denota il linguaggio vuoto).
ra+ = rara*.

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 = {anbm n≥0,m≥2} L'espressione regolare per questo linguaggio è a*bbb*.
- L = {anbn 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[modifica]

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)*