Automi riconoscitori ed espressioni regolari

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

Lo scopo di questa lezione è presentare alcuni metodi per tradurre un'espressione regolare in un automa a stati finiti. Non esiste un metodo preciso e unico per effettuare questa operazione; i differenti algoritmi producono soluzioni diverse, alcuni deterministici altri no, altri con epsilon mosse altri no.

Introduciamo dapprima la classe dei linguaggi locali, che tornerà utile per alcuni algoritmi.

Linguaggi locali[modifica]

Definiamo la classe dei linguaggi localmente testabili, chiamata anche semplicemente locale (LOC) come sotto famiglia (propria) dei linguaggi regolari . Per definirla facciamo uso delle seguenti "funzioni" di un linguaggio:

  • insieme dei caratteri iniziali:
  • insieme dei caratteri finali:
  • insieme di digrammi:
  • insieme complemento di digrammi:

Le operazioni sopra possono essere applicate con lo stesso effetto alla singola stringa anziché a un intero linguaggio.

Esempi[modifica]

Definizione[modifica]

Un lingaggio locale è un linguaggio che contiene tutte e solo le stringhe che possono essere generate a partire dai tre insiemi visti sopra:

Esempio1: è locale: tutte le stringhe ottenute da Ini, Fin e Dig sono contenute in .

Esempio2: non è locale: la stringa bbbc non è contenuta in ma rispetta le condizioni sopra citate.

Per ogni regolare non locale, esiste un altro linguaggio regolare e locale che contiene tutte le stringhe ottenibili da .

Riconoscitore[modifica]

Il riconoscitore dei linguaggi locali è molto semplice: devo verificare che il primo e ultimo carattere sia quelli cercati e che ogni coppia sia presente.

Vediamo come fare con un esempio, traduciamo il linguaggio locale:

Local-automata.png

Metodi[modifica]

Tra i molti metodi possibili, abbiamo:

  • Metodo di Thompson o strutturale: l'automa generato è in generale non deterministico e con -mosse.
  • Metodo GMY (Glushhkov, Mc Naugthon and Yamada): l'automa generato è in generale non deterministico ma senza -mosse.
  • Metodo BS (Berry and Sethi): automa deterministico

Metodo di Thompson[modifica]

L'idea del metodo Thompson è elaborare le varie componenti dell'automa partendo dalla regex ed analizzandola parte per parte. Successivamente le componenti verranno interconnesse in modo da ottenere un riconoscitore completo.

N.B. il metodo di Thompson funziona solo se assumiamo un solo stato iniziale e un solo stato finale senza, rispettivamente, archi entranti o uscenti. Nel caso in cui questo non fosse vero, è necessario sostituire con (ovvero aggiungere) un nuovo stato iniziale e/o finale per riportarci alla situazione desiderata.

L'algoritmo consiste nel prendere ogni singolo elemento della regex ed applicarne le regole seguenti per generare un piccolo automa che verrà poi assemblato:

L'espressione è rappresentata dall'automa

Thompson-epsilon.svg

Un simbolo è convertito nell'automa:

Thompson-a-symbol.svg


L'espressione ottenuta dall'unione di due sottoespressioni è convertita in

Thompson-or.svg

Lo stato va tramite un' -transazione in uno stato iniziale di o . I loro stati finali divengono intermedi e si uniscono per mezzo di -transazioni nello stato finale di N(e) chiamato .

L'espressione formata dalla concatenazione di due sottoespressioni si converte in

Thompson-concat.svg

Lo stato iniziale di è lo stato iniziale di N(e). Lo stato finale di diventa lo stato iniziale di . lo stato finale di è anche lo stato finale di .

La Kleene star di un'espressione è convertita in

Thompson-kleene-star.svg

Un' -transizione connette lo stato iniziale e finale dell' NFA . Un'altra -transizione che va dallo stato finale a quello iniziale di consente la ripetizione dell'espressione come da definizione dell'operatore Kleene star.

Metodo GMY[modifica]

Metodo BS[modifica]

Per il metodo BS sfrutteremo i linguaggi locali definiti nella prima sezione. Ricordiamo che il grande vantaggio di questo metodo è che l'automa generato è deterministico. Introduciamo questo algoritmo tramite un esempio.

Si prenda la seguente regex:

e la sua versione numerata terminata (ovvero con un carattere alla fine chiamato terminatore ):

Definiamo insieme dei successori di un carattere come segue:

Risulterà quindi che il terminatore è il carattere che segue tutti i caratteri finali

(abbiamo usato un abuso di notazione, il carattere terminatore non è propriamente parte della regex, altrimenti sarebbe da considerare il finale)

Nel precedente esempio risulterà: , , , ...

Ogni insieme corrisponde all'insieme dei simboli che si aspettano come prossimo input e il terminatore rappresenta lo stato finale. Di conseguenza lo stato iniziale risulta: .

Si applica in seguente algoritmo:

L'algoritmo BS può anche essere usato per rendere un automa deterministico, anche se l'automa non deterministico di partenza possiede -mosse. L'idea è la seguente:

  1. si ottiene una versione numerata dell'automa, aggiungendo anche un numero ad ogni -mossa;
  2. si calcolino similmente alle regex gli insieme Ini e Fol;
  3. utilizzando BS si ottenga il nuovo automa deterministico.