Linguaggi ed espressioni regolari

Da Wikiversità, l'apprendimento libero.
Jump to navigation Jump to search
lezione
Linguaggi ed espressioni regolari
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Linguaggi formali e automi
Avanzamento Avanzamento: lezione completa al 100%.

In questa lezione analizzeremo la famiglia delle espressioni regolari (in inglese regular expression o, in forma abbreviata, regexp, regex o RE) di cui si invita a leggere come introduzione la relativa pagina di Wikipedia.

Definizione[modifica]

Formalmente definiamo espressione regolare una stringa costruita su un alfabeto e in unione ai seguenti metasimboli:

  • : insieme vuoto
  • : unione (notazione alternativa: )
  • : concatenazione
  • : star
  • : parentesi

Una RE è detta ben formata se si presenta in una delle seguenti forme:

  • o
  • o (notazione alternativa)

dove e sono a loro volta espressioni regolari. Si noti che la precedenza degli operatori è:

Definiamo inoltre altri operatori non essenziali ma frequentemente usati, utilizzando solo le proprietà sopra descritte:

  • (potenza)
  • con (ripetizione)
  • (intervalli ordinati)

Altri operatori possono essere quelli insiemistici teorici: intersezione, differenza e complemento. Una espressione regolare che contiene questi operatori è detta espressione regolare estesa. Nota: Il potere espressivo di una RE estesa non è maggiore di quello di una RE standard.

Definizione di linguaggio regolare[modifica]

Diciamo che un linguaggio è un linguaggio regolare se è denotato da una RE. Formalmente, un linguaggio regolare è un linguaggio su un alfabeto che ha una corrispondente RE in accordo con la seguente tabella:

Espressione Linguaggio


Denotiamo con la famiglia di tutti linguaggi regolari e con la famiglia di tutti i linguaggi finiti (cioè con cardinalità finita).

Allora possiamo dire che:

(intuibile: un linguaggio finito può sempre essere visto come l'unione di un numero finito di stringhe, ognuna delle quali concatenazione di un numero finito di simboli dell'alfabeto)

Derivare il linguaggio dalla RE[modifica]

Per derivare il linguaggio dobbiamo definire alcuni concetti supplementari.

Sottoespressione[modifica]

Definiamo sottoespressione (in inglese subexpression o SE) una ben parentizzata sottostringa di una RE che si presenta nelle parentesi più esterne.

Chiariamo con un esempio. Sia data la RE:

questa RE ha due SE: e , mentre e NON sono SE di , ma sono SE di .

Versione numerata[modifica]

Definiamo 'versione numerata di una RE, la RE a cui vengono aggiunti i numeri alle lettere che compongono la RE, in modo da differenziale le lettere uguali. Anche qui chiariamo il concetto con un esempio:

la sua versione numerata è:

Questa notazione è importante per definire l'ambiguità di un linguaggio (introdotta nelle sezioni successive).

Scelta e derivazione[modifica]

Diciamo che una RE è una scelta (in inglese choice) di un'altra RE nei seguenti casi:

  • è una scelta di
  • è una scelta di e
  • è una scelta di

Diciamo che una SE deriva da (scritto come se:

  • è una scelta di ;
  • oppure, è una scelta di per ogni

La derivazione può avvenire più volte allo stesso modo. In questo caso scriviamo:

    • se , , ..., con fisato
    • se , , ..., con
    • se , , ..., con

Esempi[modifica]

  • o equivalentemente o ancora
  • o equivalentemente o ancora

Linguaggio definito da un RE[modifica]

Il linguaggio definito da una espressione regolare è:

Diciamo che due RE sono equivalenti se definiscono lo stesso linguaggio.

Ambiguità delle RE[modifica]

Una stringa di un linguaggio regolare può essere derivato dalla RE in modi differenti, cioè attraverso distinte derivazioni. Diciamo che una RE è ambigua se esiste una stringa derivabile attraverso due distinte derivazioni che non differiscono solo dall'ordine di applicazione.

Esempio:

Ambigua, due modi di derivazione di :

Condizione sufficiente affinché una RE sia ambigua, se il linguaggio generato dalla RE in versione numerata include due stringhe che coincidono a meno dei numeri.

Esempio:

Genera:

  1. ...

Come si vede eliminando i numeri, la stringa 2 coincide con la stringa 7, perciò la RE è ambigua.

Proprietà di chiusura[modifica]

« Un insieme è chiuso rispetto a un'operazione se e solo se ogni insieme ottenuto applicando l'operazione ai membri dell'insieme originale, l'insieme ottenuto è contenuto nell'insieme originario »

è chiuso rispetto alla concatenazione, unione e star (quindi anche per gli altri operatori sopra descritti).

Link e riferimenti[modifica]

Esempi pratici - https://www.evemilano.com/2014/07/come-funzionano-le-espressioni-regolari-regex/

Altri progetti[modifica]