Automi di Riconoscimento

Nei precedenti paragrafi abbiamo discusso la possibilità di "generare" un linguag-gio come l'insieme delle stringhe derivatili da una grammatica a struttura di frase.

Abbiamo anche collegato le proprietà di decidibilità di un linguaggio alla espres-sività delle grammatiche che lo generano e alla forma delle loro produzioni. Ma in questo ambito anche gli automi giocano un ruolo di fondamentale importanza e, in particolare, possono essere adoperati per determinare i linguaggi L in modo alternativo alle grammatiche, volto non a generare, ma a riconoscere e accettare le stringhe di L. Un automa, infatti, legge uno alla volta i simboli di ogni stringa che gli viene proposta e, alla fine dell'esame, "certifica" se la stringa appartiene o

no al linguaggio interessato.

In realtà, si possono formare varie classi di automi, anzi ogni classe di gramma-tiche nella gerarchia di Chomsky si può collegare a una corrispondente classe di automi in modo tale che differenti poteri espressivi delle classi di grammatiche si rispecchino in differenti poteri riconoscitivi delle relative classi di automi. Del resto abbiamo già visto nello scorso paragrafo che alla classe di tutte le grammati-che a struttura di frase corrisponde quella delle Macchine di Turing, nel senso grammati-che un linguaggio è accettato da una MdT se e solo se è generato da una grammatica di tipo O. Allo stesso modo si vede che:

• alla classe delle grammatiche regolari corrisponde la classe dei così detti

automi a stati finiti,

• alla classe delle grammatiche libere dal contesto corrisponde la classe degli

automi a pila,

• alla classe delle grammatiche dipendenti dal contesto corrisponde la classe degli

automi linearmente limitati.

Diamo adesso qualche breve cenno su queste tre classi di automi e sulle diverse formalità che esse prevedono per l'operazione di riconoscimento delle stringhe di un linguaggio.

Da un punto di vista esteriore, ogni automa, così come ogni MdT, si compone di un dispositivo di controllo con un numero finito di stati, di una testina di lettura e scrittura e di un nastro suddiviso in celle. La stringa in input viene scritta su que-sto nastro da sinistra verso destra, un carattere per ogni cella. I quadri a sinistra e a destra dell' input sono riempiti dal simbolo bianco *. All'inizio del riconoscimen-to, la testina di lettura e scrittura esamina il primo simbolo dell'input e il controllo è nello stato iniziale. A questo punto gli automi si differenziano in ragione delle modalità previste per il loro funzionamento.

Per esempio, in un

automa a stati finiti

la stringa in input viene scorsa da sinistra verso destra, un simbolo alla volta: a ogni passo l'automa legge il carattere sul nastro, cambia il suo stato secondo quanto gli ordina una fissata funzione di tran-sizione e sposta finalmente la sua testina di un passo verso destra. Esaminata tutta la stringa in ingresso, l'automa si arresta, ed è proprio lo stato con cui si ferma a stabilire se l' input appartiene o no al linguaggio. Un automa a stati finiti si può dunque pensare come una MdT con capacità ridotte: licenza di leggere ma non di scrivere, permesso di spostarsi solo a destra. Come detto, si mostra che la classe degli automi a stati finiti corrisponde alla classe dei linguaggi di tipo 3: vale a dire, un linguaggio è riconosciuto da un qualche automa a stati finiti se e solo se è regolare.

La limitazione delle capacità di riconoscimento degli automi a stati finiti si ri-conduce al fatto che essi dispongono soltanto di una memoria finita (quella che è loro assicurata dai loro stati). Per questo motivo essi non sono in grado di rico-noscere linguaggi che richiedono invece di ricordare una quantità di informazione illimitata. Si pensi per esempio al linguaggio

L = {ai bi :

i E

N, i > 1}

già considerato in § 5.6 e all'inizio di § 5.7. Per riconoscerne una stringa db i bisogna ricordare il numero i degli a letti prima di incontrare il primo

b,

in modo da poter poi controllare che i

b

che completano la stringa siano altrettanti. Nes-sun automa a stati finiti ha questa potenzialità di memoria (e del resto

L

non è regolare). Per migliorare le capacità di riconoscimento degli automi a stati finiti, possiamo pensare a nuovi modelli che dispongano di una memoria ausiliare illi-mitata e svolgano ogni mossa della loro computazione in dipendenza non solo del carattere letto e dello stato del dispositivo di controllo, ma anche della informa-zione precedentemente accumulata nella memoria. Un

automa a pila

corrisponde a questi requisiti: ha il suo dispositivo di controllo a stati finiti, la sua testina di lettura e scrittura, il suo nastro e, in più, una memoria ausiliaria a pila di lunghezza infinita cui però può accedere solo dalla testa. Si mostra allora che la classe degli automi a pila corrisponde a quella dei linguaggi di tipo 2: un linguaggio è ricono-sciuto da un automa a pila (non deterministico) se e solo se è libero dal contesto.

Così la disponibilità di una memoria ausiliaria potenzialmente illimitata non è sufficiente a riconoscere ogni linguaggio a struttura di frase: ci sono infatti lin-guaggi dipendenti dal contesto che nessun automa a pila sa riconoscere. In effetti, quello che è essenziale in questo ambito più generale non è tanto una memoria ausiliaria illimitata, quanto la libertà di poterne disporre senza eccessivi vinco-li. Nel caso dei linguaggi dipendenti dal contesto, allora, basta contare su di una memoria linearmente limitata dalla lunghezza dell'input e accessibile senza re-strizioni. L'automa che ne risulta viene chiamato

automa linearmente limitato.

La classe degli automi linearmente limitati corrisponde esattamente alla classe dei linguaggi di tipo 1.

5.11 Esercizi

1. Si definiscano, se possibile, grammatiche regolari che generano:

(a) le stringhe di lunghezza arbitraria che iniziano con un simbolo assegnato, (b) le stringhe di lunghezza al più 6 che iniziano con un simbolo prefissato.

2. A quale classe nella gerarchia di Chomsky appartiene il linguaggio delle strin-ghe su {a,

b,

c} che contengono un numero dispari di a, un numero dispari di

b

e un numero pari di c?

3. A quale classe nella gerarchia di Chomsky appartengono i seguenti linguaggi?

• L i =

{anan

i n E N, n > O},

• L2 =

{a n ban I

n E N},

• L3 = {anbancan

i

^{n E N}.}

4. Il linguaggio

L =

{ai b22

I ⁱ

^E N, i > O} è o no libero dal contesto?

5. Sia

G = (N, T, P, 51)

una grammatica libera dal contesto tale che ogni pro-duzione in P è di una delle forme A ---> wB o A > Bw o A —> w, dove w E

T* e A, B

E

N. L(G) è

regolare?

6. Si provi che ogni grammatica dipendente dal contesto è monotona, e vicever-

sa si dia un esempio di una grammatica monotona che non è dipendente dal contesto.

7. Sia K, al solito, l'insieme dei numeri naturali x tali che la x-ma MdT converge su x. K è un linguaggio di tipo 0? È di tipo 1, o 2, o 3? E che si può dire del suo complementare N — K?

Riferimenti bibliografici Un ottimo riferimento generale per approfondire tutti gli argomenti di questo capitolo è [55], che espone con chiarezza, semplicità e completezza la teoria dei linguaggi formali e degli automi e discute molti pro-blemi di decidibilità per classi di linguaggi e automi. Per una trattazione estesa sulla teoria degli automi si considerino [8] e [54]. Per le grammatiche a struttura di frase si consultino anche [13] e [14].

L' indecidibilità del problema dell'equivalenza per grammatiche libere dal conte-sto è trattata in [76], quella del problema di riconoscere linguaggi vuoti tra quelli dipendenti dal contesto è in [29]. Il problema della complementazione dei lin-guaggi dipendenti dal contesto è risolto in [58] e [105]. I fondamenti della teoria degli alberi si possono trovare per esempio in [40].

Segnaliamo anche [81], dove vengono studiate le varie classi della Gerarchia di Chomsky, le loro relazioni con gli automi e le tecniche di parsing dei linguaggi:

buona parte del libro è poi dedicata alla descrizione formale dei linguaggi naturali.

[81] dimostra anche la coincidenza tra i linguaggi dipendenti dal contesto e quelli generati da grammatiche monotone.

Per le applicazioni della teoria dei linguaggi formali alla definizione sintattica e alla compilazione dei linguaggi di programmazione si consiglia finalmente la lettura dei testi [4, 6].

Per approfondimenti sull'uso degli automi a stati finiti come modelli di sistemi concorrenti e distribuiti si faccia riferimento a [79].

6

Nel documento Carlo Toffalori Flavio Corradini Stefano Leonesi Stefano Mancini. Teoria della computabilità e della complessità. McGraw-Hill (pagine 102-106)