Espressioni regolari

Cosa sono le espressioni regolari

Le espressioni regolari (ER) sono un tipo di notazione usata per definire i linguaggi formali.

Sono strettamente legate agli automi a stati finiti non deterministici (NFA) perché descrivono i linguaggi di un'automa.

Tuttavia, le ER possono definire soltanto i linguaggi regolari. E' un limite da ricordare.

Nota. Le espressioni regolari sono uno strumento più potente per descrivere il linguaggio rispetto a un automa. Per elaborare le stringhe da accettare si basano su un approccio dichiarativo.

Le espressioni regolari atomiche

Le espressioni regolari atomiche sono espressioni elementari che identificano delle unità (atomi).

• Una qualsiasi lettera dell'alfabeto e∈E è un'espressione regolare atomica. Definisce il linguaggio $$ L(e) = \{ e \} $$
• L'insieme vuoto dei simbolo Ø è un'altra espressione atomica. $$ L(Ø) = \{ \} $$
• Il simbolo della parola vuota epsilon ε è un'altra espressione regolare atomica $$ L(ε)= \{ ε \} $$

Sono dette atomi perché sono le unità elementari nella costruzione delle espressioni regolari più complesse.

Gli operatori delle espressioni regolari

Gli operatori delle espressioni regolari sono usati per costruire le espressioni regolari più complesse.

• Unione (+)
  Date due espressioni regolari α e β, l'operatore unisce le due espressioni in un'unica espressione regolare complessa. $$ α+β $$

  Esempio. Date due espressioni $$ L(a)=\{a\} \\ L(b)=\{b\} $$ La somma è $$ L(a)+ L(b) = \{a\} + \{b\}= \{ a, b \} $$

• Concatenazione (·)
  Date due espressioni regolari α e β, l'operatore · della concatenazione scrive le due espressioni in un'unica espressione regolare complessa rispettando l'ordine di presentazione. $$ α·β $$ Il simbolo · si omette per praticità. $$ αβ $$

  Esempio. Date due espressioni $$ L(a)=\{a\} \\ L(b)=\{b\} $$ La concatenazione è $$ L(a)·L(b) = \{a\} · \{b\}= \{ ab \} $$

• Stella di Kleen (*)
  Date due espressioni regolari α e β, l'operatore * determina la stella di Kleen creando un'unica espressione regolare complessa. La stella di Kleen si applica soltanto sul simbolo immediatamente precedente a* oppure sul gruppo di simboli immediatamente precedenti posti tra parentesi (ab)*.
  

  Esempio. Date due espressioni $$ L(a)=\{a\} \\ L(b)=\{b\} $$ La concatenazione è $$ L(a)·L(b)* = \{a\} · \{b\}*= \{ab^n \} = \{ ab, abb, abbb , ... \} $$

La stella di Kleen ha priorità più alta degli altri. Seguita dalla concatenazione.

L'unione ha priorità più bassa.

Esempio. Questa espressione regolare complessa è composta dalla somma, la concatenazione e la stella di Kleen $$ 0+01* $$ Seguendo le priorità, devo prima eseguire il calcolo della stella di Kleen sull'ultimo simbolo {1ⁿ}, poi la concatenazione e infine la somma (unione).

Per alterare l'ordine di priorità delle operazioni o per raggruppare più simboli si usano le parentesi tonde.

Esempio. Questa espressione regolare complessa è composta dalla somma, la concatenazione e la stella di Kleen $$ (0+0)1* $$ Seguendo le priorità, prima svolgo la somma tra parentesi, poi calcolo della stella di Kleen sull'ultimo simbolo {1ⁿ} e infine applico la concatenazione.

Le espressioni regolari equivalenti

Le espressioni regolari equivalenti sono espressioni regolari che generano lo stesso linguaggio.

Esempio

Queste tre ER generano lo stesso linguaggio

$$ L(a)=L(aa)=L(a*) $$

La classe dei linguaggi regolari

Una classe dei linguaggi regolari è l'insieme dei linguaggi {L} che sono espressi da un'espressione regolare.

Come scrivere le espressioni regolari di un linguaggio

Ho un alfabeto composto dai simboli 0 e 1

$$ E= \{ 0,1 \} $$

Devo trovare l'espressione regolare che descrive il linguaggio con parole E* che hanno 1 come secondo simbolo e terminano con 00.

$$ L= \{ 0100, 1100, 01100, 11100, 010100 ... \} $$

Sapendo che E={0,1} ogni parola di E* può essere scritta nel seguente modo:

$$ u=(0+1)* $$

Ogni parola w di L può invece essere scritta nel seguente modo:

$$ w \in u_1 \cdot 1 \cdot u_2 \cdot 00 $$

Sostituendo alle incognite u₁ e u₂ l'espressione (0+1) e ottengo

$$ w \in (0+1) \cdot 1 \cdot (0+1)* \cdot 00 $$

Elimino il simbolo della concatenazione

$$ w \in (0+1) 1 (0+1)* 00 $$

Quindi, il linguaggio L è determinato dalla seguente espressione regolare:

$$ L= \{ (0+1)1(0+1)*00 \} $$

Nota. Dato un linguaggio L, non sempre è possibile trovare le espressioni regolari (ER) che lo determinano, perché le ER possono definire soltanto il linguaggio regolare.

E così via.