Automi e linguaggi formali

Automi e linguaggi formali

La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni diverse, dai processi che si svolgono in tempi discreti alle catene di molecole, e ciò conferisce alla teoria un aspetto interdisciplinare. La teoria matematica applicata, che si è sviluppata parallelamente alla necessità di formalizzare e descrivere i processi legati all'uso del calcolatore e agli strumenti di comunicazione, ha un'origine che risale ai lavori di logici dei primi decenni del Novecento, quali Emil L. Post, Alonzo Church e Alan M. Turing, che erano motivati dalla necessità di dare un fondamento alla nozione di dimostrazione matematica, sulla via inaugurata da David Hilbert. Dopo la Seconda guerra mondiale, in conseguenza dello sviluppo di calcolatori e sistemi di telecomunicazione e del rinnovato interesse per lo studio delle funzioni del cervello umano, Claude E. Shannon, Stephen C. Kleene e John von Neumann hanno ampliato l'approccio originario. Negli anni Sessanta, l'interesse dei linguisti è stato stimolato dai lavori di Noam A. Chomsky, sostenitore dell'uso dei metodi formali nella descrizione dei linguaggi naturali. Lo sviluppo della biologia molecolare ha poi portato a considerare le catene di molecole, formate dai genomi, come successioni di simboli sull'alfabeto costituito dalle basi: un ulteriore motivo per occuparsi di proprietà come le ripetizioni di simboli o delle affinità tra successioni.

Nella classica gerarchia di Chomsky, si descrivono i linguaggi formali secondo quattro livelli di complessità crescente: a stati finiti, liberi dal contesto (context-free), dipendenti dal contesto (context-sensitive) e ricorsivamente computabili. Cercheremo di dare un'idea di questi livelli, fornendo le necessarie definizioni in modo piuttosto informale e sottolineando gli sviluppi più recenti. Nella prima parte tratteremo della teoria degli automi finiti, mettendo in evidenza i legami con altri campi della matematica, in particolare con la teoria dei semigruppi e dei linguaggi razionali. Prenderemo in considerazione i legami con la logica nonché l'estensione dei linguaggi a oggetti infiniti e introdurremo la dinamica simbolica, attraverso la nozione di sistema dinamico simbolico. Nella seconda parte ci occuperemo del secondo livello della gerarchia di Chomsky, i linguaggi liberi dal contesto, sottolineando il legame tra grammatiche libere dal contesto e automi 'a pila' e fornendo recenti risultati sugli automi a pila deterministici. Come nel caso degli automi finiti, menzioneremo i legami con la teoria dei gruppi, inclusi alcuni importanti risultati sui gruppi liberi dal contesto. Il quarto e ultimo livello della gerarchia è costituito dalla classe dei linguaggi ricorsivamente enumerabili, introdotta mediante le macchine di Turing. Definiremo la corrispondente classe di funzioni ricorsive intere e tratteremo le classi di complessità P, NP e PSPAZIO, includendo anche il famoso problema aperto P≠NP.

Considereremo quindi due campi di ricerca vicini allo studio dei linguaggi formali: quello delle serie formali, che ha importanti applicazioni nella combinatoria enumerativa e nell'analisi degli algoritmi, e la combinatoria delle parole, una branca della combinatoria molto attiva, che ha collegamenti con vari settori dell'algebra e della teoria dei numeri. Discuteremo infine le applicazioni dei linguaggi formali e degli automi, che riguardano la progettazione di software, i compilatori, il trattamento di testi e la loro compressione, il trattamento dei linguaggi naturali e gli studi sul genoma.

Automi finiti

Un automa finito è il modello più semplice di computazione e, più in generale, di comportamento di un sistema: si tratta di un controllo discreto dotato di memoria finita. La sua prima trattazione esplicita risale a un lavoro di Stephen C. Kleene degli anni Cinquanta del Novecento e il primo teorema che lo riguarda è l'equivalenza tra il modello dell'automa finito e la descrizione di successioni di simboli ottenute utilizzando i tre simboli logici primitivi di unione, prodotto di insiemi e iterazione. Le espressioni costruite in questo modo sono dette 'espressioni razionali'; un linguaggio descritto da un'espressione razionale è detto anch'esso razionale. Il teorema di Kleene afferma che un linguaggio è razionale se e solo se è riconosciuto da un automa finito. Tale risultato ha una dimostrazione costruttiva che fornisce un algoritmo implementato in numerosi sistemi pratici. L'articolo di Kleene ha un precursore in un lavoro di Warren Sturgis McCulloch e Walter Pitts, che si proponevano di descrivere il comportamento del cervello umano facendo riferimento a un modello di neuroni e sinapsi. I primi articoli di teoria degli automi hanno anche legami con la teoria dei circuiti: un circuito sequenziale, nel quale l'uscita dipende da un segnale di entrata, è ben descritto da un automa finito.

fig. 2

La fig. 2 rappresenta un automa finito con due stati: 1 è lo stato iniziale, mentre 1 e 2 sono entrambi finali. Gli archi sono etichettati con i simboli a e b. L'insieme delle parole, etichette di cammini dallo stato iniziale a uno stato finale, è l'insieme di tutte le parole su a e b nelle quali a è sempre immediatamente seguito da b. Per il teorema di Kleene, questo insieme di parole si può anche descrivere con un'espressione razionale, e cioè: (ab+b)*(ε+a), dove ε denota la parola vuota, + l'unione e l'asterisco l'iterazione.

La star-height

La star-height (altezza, o profondità, dell'operazione di iterazione) di un linguaggio razionale X si definisce semplicemente come il più piccolo numero, su tutte le espressioni razionali che descrivono X, di simboli di iterazione nidificati che compaiono nell'espressione. Quindi la star-height è 0 se e soltanto se il linguaggio è finito, ossia non vi sono iterazioni. La star-height dell'espressione che descrive un linguaggio non è sempre la minima possibile. Per esempio, le espressioni (a*b)*a* e (a+b)* descrivono entrambe l'insieme di tutte le parole su a e b; la prima ha star-height 2, la seconda 1. Il problema del calcolo della star-height di un linguaggio razionale è stato sollevato fin dagli albori della teoria degli automi e risolto, in linea di principio, da Kosaburo Hashiguchi, che ha dimostrato che la star-height è ricorsivamente computabile. Restano da studiare metodi efficienti per calcolarla, oppure dimostrare che non ne esistono. Strettamente collegato a questo problema ve ne è un altro ancora aperto: quale sia il minimo valore della star-height di espressioni razionali più generali, cioè quelle nelle quali si ammette l'uso della complementazione. Non si conoscono attualmente esempi di star-height maggiore di 1 per queste espressioni.

Teoremi di decomposizione

Due automi finiti possono essere composti a formarne un terzo. Ciò si vede facilmente quando gli automi hanno un'uscita (output), allorché definiscono funzioni sulle parole che possono essere composte nel solito modo. Negli anni Sessanta del Novecento, Kenneth Krohn e John L. Rhodes hanno ottenuto un teorema di decomposizione che afferma che ogni automa finito si può ricavare componendo automi di due tipi: (a) automi a gruppo, nei quali le azioni dei simboli sugli stati sono biunivoche, e (b) reset, che memorizzano soltanto l'ultimo simbolo letto. Questo risultato si applica ai semigruppi finiti e fornisce un teorema di decomposizione per semigruppi; nel caso di gruppi finiti si ha la nota decomposizione nei gruppi semplici che si ottengono a partire da una serie di composizione. Il calcolo della complessità di un semigruppo finito, nel senso del minimo numero di gruppi che compaiono in una decomposizione, è un problema aperto.

Semigruppi e varietà

Fu presto compreso che gli automi finiti sono strettamente legati ai semigruppi finiti, ottenendo così l'analogo algebrico della definizione di riconoscibilità da parte di un automa finito. Si possono infatti caratterizzare i linguaggi razionali come quelli che sono riconosciuti da un morfismo su un semigruppo finito, cioè della forma X=φ⁻¹(Y) per qualche morfismo φ:A*→S su un semigruppo finito S, con Y⊂S. Esiste altresì un semigruppo S minimo per ogni X, detto semigruppo sintattico di X. Il primo importante risultato in questa direzione è il teorema di Schützenberger sui linguaggi senza asterischi (star-free). Diamo alcune definizioni. Un linguaggio star-free si può ottenere limitando le operazioni razionali, escludendo l'operazione di iterazione, ma ammettendo tutte le operazioni booleane, compresa la complementazione. Per esempio, l'insieme delle successioni di 0 e 1 con le due cifre che si alternano è un linguaggio star-free, in quanto si può ottenere come il complementare dell'insieme delle successioni aventi qualche blocco 00 o 11. Un semigruppo finito S inoltre si dice aperiodico se esiste un intero n≥1 tale che per ogni x∈S si abbia xⁿ=xⁿ. Il teorema di Schützenberger afferma che un linguaggio razionale è star-free se e soltanto se è riconosciuto da un semigruppo aperiodico.

La teoria delle varietà di linguaggi razionali si deve a Samuel Eilenberg e rappresenta, in un certo senso, il punto di arrivo di sforzi precedenti e la sistemazione di molti fatti noti in un quadro unificato. Una varietà di semigruppi è formalmente una famiglia di semigruppi finiti, chiusa rispetto ai morfismi, al prodotto diretto di due semigruppi e ai sottosemigruppi; tecnicamente la si dovrebbe chiamare pseudovarietà, in quanto non è chiusa rispetto a prodotti diretti arbitrari, come nella teoria di Birkhoff. Esempi principali ne sono la varietà dei semigruppi aperiodici e molte sue sottovarietà. Un teorema generale afferma che esiste una corrispondenza tra varietà di semigruppi e famiglie di linguaggi razionali, dette anche varietà di linguaggi, nel senso che i semigruppi sono quelli sintattici dei corrispondenti linguaggi. La varietà dei semigruppi aperiodici corrisponde così a quella dei linguaggi star-free.

Una nozione interessante è quella di localizzazione di una varietà V: si dice che un semigruppo S appartiene localmente alla varietà V se, per ogni idempotente e∈S, il semigruppo eSe appartiene a V. Si può dimostrare che la famiglia di questi semigruppi è ancora una varietà, che si denota con L_V. Per esempio, la varietà dei semigruppi aperiodici coincide con la varietà dei semigruppi localmente banali. Un altro esempio interessante è dato dalla varietà dei linguaggi localmente testabili. Un linguaggio X si dice localmente testabile se esiste un intero k tale che la proprietà w∈X dipende soltanto dall'insieme dei blocchi di w che hanno lunghezza k. Un semigruppo è idempotente se x=x² e commutativo se xy=yx, identicamente. Per un importante teorema di Robert McNaughton, Janusz A. Brzozowski e Imre Simon, un linguaggio è localmente testabile se e solo se il suo monoide sintattico è localmente idempotente e commutativo.+1

Automi e logica

Si deve a Richard Büchi l'idea di introdurre gli automi finiti nel contesto, a prima vista a loro estraneo, della logica formale. Dai lavori di Kurt Gödel degli anni Trenta del Novecento era noto che la teoria logica degli interi con le operazioni + e × è indecidibile; ciò lasciava aperta la ricerca di sottoteorie decidibili. Un primo risultato fu ottenuto da Thomas Pressburger, il quale dimostrò che la teoria degli interi con + come unico operatore è decidibile. Büchi dimostrò negli anni Sessanta la decidibilità di un'altra porzione della logica: la teoria monadica del secondo ordine degli interi con successore. La dimostrazione si basa su una riduzione ad automi finiti e assimila un insieme di interi a una successione binaria infinita: per esempio, l'insieme dei numeri pari corrisponde alla successione 1010101… I lavori di Büchi hanno aperto un nuovo campo di ricerca, che si sviluppa in due direzioni, l'una riguardante l'estensione della teoria degli automi finiti a parole infinite, l'altra lo studio dei legami tra teoria degli automi e logica formale. In questo quadro, Büchi ha dimostrato che i linguaggi razionali sono proprio quelli che si possono definire in un linguaggio logico che permetta di confrontare le posizioni delle lettere nelle parole e l'uso di quantificatori su insiemi di posizioni (teoria monadica del secondo ordine degli interi con 〈). Ciò ha aperto la strada alla caratterizzazione in termini di automi di altre classi di teorie logiche. Una delle prime motivazioni per lo studio dei linguaggi star-free è stata l'osservazione da parte di McNaughton che essi corrispondono alla parte del primo ordine di detta teoria, ossia a quella priva di variabili di insiemi. Più recentemente è stata introdotta una variante di questa logica, la logica temporale, che è applicata alla verifica dei programmi.

Parole infinite e alberi

Il lavoro di Büchi ha dato luogo a una teoria dei linguaggi, detti talvolta ω-linguaggi, nella quale gli elementi sono parole infinite e tutte le nozioni note nel caso finito sono estese al caso infinito, anche se le dimostrazioni sono notevolmente più difficili. Per esempio, i fatti fondamentali riguardanti i linguaggi razionali, come la chiusura rispetto alle operazioni booleane, nel caso infinito diventano un risultato molto delicato, dovuto a Büchi, che fa uso del teorema di Ramsey. Nel caso infinito, gli algoritmi di determinazione degli automi finiti diventano, analogamente, un difficile teorema di McNaughton. Oltre alle parole, si possono definire automi su alberi, anche infiniti: il criterio ispiratore è semplicemente quello per cui processare un albero dall'alto in basso significa duplicare copie dell'automa in ogni figlio del vertice attuale. Lo stato raggiunto nelle cosiddette foglie (o gli stati infinitamente ripetuti se l'albero è infinito) determina l'accettazione o meno dell'albero da parte dell'automa. Il risultato più noto in questo campo è il teorema di complementazione di Michael O. Rabin. Il significato della dimostrazione si può meglio comprendere tenendo presenti alcune idee elaborate da Juri Gurevich e Leo Harrington, il cui tratto distintivo è l'uso di strategie vincenti in giochi combinatori, secondo la seguente impostazione: si può descrivere e processare un albero con un automa come un gioco in cui sono coivolte due persone, di cui una (l'Automa) sceglie una transizione dell'automa, l'altra (l'Esploratore) sceglie una direzione nell'albero. L'Automa ha una strategia vincente se e solo se l'automa accetta l'albero.

Dinamica simbolica

Gli automi finiti hanno numerose relazioni con la dinamica simbolica sviluppata originariamente da Harold M. Morse e Gustav A. Hedlund, una teoria che studia sistemi dinamici simbolici costituiti da insiemi di parole doppiamente infinite, invarianti rispetto allo scorrimento (shift) e topologicamente chiusi. L'esempio più semplice è l'insieme delle successioni binarie su {a,b} nelle quali non compaiono mai due b consecutive, sistema detto della sezione aurea. Di particolare interesse sono i subshifts di tipo finito introdotti da Robert F. Williams, che si possono definire proibendo che compaiano alcune parole, in numero finito. Così il sistema della sezione aurea è un subshift di tipo finito, mentre l'insieme delle parole prive di quadrati non lo è. L'entropia h(S) di un subshift S è il limite di (1/n)logu_n, dove u_n è il numero dei possibili blocchi di lunghezza n di S. Per il sistema della sezione aurea si ha u_n=u_n+u_n, per cui l'entropia è logφ, dove φ è la sezione aurea, il che ne giustifica il nome. Un bel risultato della teoria è il teorema di Krieger, che afferma che è possibile immergere strettamente un subshift di tipo finito S in un altro T se e solo se: (a) h(S)〈h(T); (b) p_n(S)≤p_n(T), per n≥1, dove p_n(S) è il numero di punti di periodo n in S. I subshifts di tipo finito hanno uno stretto legame con i codici circolari che si studiano nella teoria dei linguaggi formali.

Automi e gruppi

Nella teoria dei gruppi, la teoria computazionale è una branca che si occupa di computazioni con i gruppi, in particolare quelli presentati con generatori e relazioni. Molti algoritmi classici, come l'algoritmo di Todd-Coxeter per l'enumerazione delle classi laterali di un sottogruppo, si possono considerare come algoritmi su automi. Una rappresentazione di permutazione di un gruppo finito è un caso particolare di automa finito. La teoria dei gruppi automatici ha origine nel lavoro di molti ricercatori, fra i quali geometri come William P. Thurston e esperti della teoria computazionale dei gruppi come John J. Cannon. Un gruppo si dice automatico se si può rappresentare come un insieme R di parole su un alfabeto A, in modo che per ogni a∈A, la relazione (r,s) su R definita da ra__=s sia razionale sincrona (x_ denota l'elemento di R corrispondente a x). Una relazione tra parole è razionale sincrona se è un sottoinsieme razionale di (A×A)*, a meno di un'aggiunta (padding) a destra per rendere di uguale lunghezza le parole di una coppia. I risultati fondamentali di questa teoria mostrano come i gruppi automatici abbiano proprietà utili, per esempio il problema della parola è facilmente risolubile, e come gruppi interessanti, per esempio i gruppi discreti della geometria iperbolica o gruppi iperbolici, siano automatici.

Grammatiche libere dal contesto

La nozione di grammatica libera dal contesto (context-free) è tecnicamente semplice: si tratta di un sistema di regole di riscrittura che servono a formare insiemi di parole su un dato alfabeto. Chomsky se ne occupò esplicitamente nel ricercare un modello per la sintassi dei linguaggi naturali. Le grammatiche sono dette a struttura di frase e si basano su idee di analisi sintattica introdotte da Zelig Harris negli anni Quaranta del Novecento, i cui precedenti si possono riconoscere nei lavori sui sistemi formali condotti da logici, in particolare Alan Turing, Axel Thue e Emil Post. Parallelamente, e in modo apparentemente indipendente, lo stesso concetto è stato sviluppato dai primi inventori dei linguaggi di programmazione, in particolare da John W. Backus, che ha utilizzato la forma detta ora BNF (Backus-Naur form) per descrivere la sintassi del linguaggio ALGOL.

Linguaggi liberi dal contesto. Una grammatica libera dal contesto è un insieme di regole della forma x→w, dove x è un simbolo non terminale (variabile) e w una parola sull'alfabeto misto di simboli terminali e non terminali. Una derivazione consiste nel sostituire un certo numero di volte una variabile mediante l'applicazione di una regola. Il linguaggio generato dalla grammatica è l'insieme delle parole sull'alfabeto terminale che si possono derivare a partire da un simbolo iniziale detto assioma. Per esempio, la grammatica con una variabile σ e due simboli terminali +, v e con le due regole σ→+vv e σ→v, genera tutte le espressioni additive nella notazione prefissa polacca con v come simbolo operando. Il linguaggio generato è anche detto linguaggio di Lukasiewicz. Un linguaggio è libero dal contesto se e solo se è generato da una grammatica libera dal contesto. È facile dimostrare che i linguaggi liberi dal contesto sono chiusi rispetto a un certo numero di operazioni, compresa l'intersezione con un linguaggio razionale, ma non rispetto alla complementazione.

Automi a pila. La nozione di linguaggio libero dal contesto è strettamente legata a quella di automa a pila. Si tratta di un automa non deterministico, con una memoria che può essere illimitata, ma accessibile unicamente attraverso una modalità ristretta detta pila, nella quale è permesso l'accesso soltanto all'ultimo elemento, in un sistema first in-last out. Una parola è accettata da questo automa se esiste un calcolo che porti alla pila vuota. Un risultato elementare afferma che un linguaggio è libero dal contesto se e solo se è accettato da un automa a pila. Il problema dell'equivalenza tra automi a pila (non deterministici) è un problema indecidibile; è infatti chiaramente equivalente a quello dell'equivalenza tra grammatiche libere dal contesto. Un problema rimasto a lungo aperto è la decidibilità dell'equivalenza di automi a pila deterministici; esso è stato risolto affermativamente da Géraud Sénizergues.

Gruppi liberi dal contesto. Un esempio fondamentale di linguaggio libero dal contesto è il linguaggio di Dyck (dal nome di uno studioso di teoria dei gruppi, il cui contributo risale però a un periodo precedente rispetto a quello delle grammatiche libere dal contesto). È il linguaggio delle espressioni ben formate che utilizzano n tipi di parentesi ed è generato dalla grammatica le cui regole sono S→a_nSa__n, per n=1,2,… più la regola S→ε. Una versione con un più elevato grado di simmetria utilizza anche le regole S→a__nSa_n. Si tratta in pratica dell'insieme delle parole sull'alfabeto A_n∪A__n equivalenti all'identità nel gruppo libero su A_n. Più in generale, un gruppo si dice libero dal contesto se ammette una presentazione G=〈A∣R〉 tale che l'insieme L(G) delle parole su A_n∪A__n che cancellano modulo le relazioni di R è un linguaggio libero dal contesto. Un gruppo libero è libero dal contesto in quanto il linguaggio di Dyck lo è. Anche un gruppo finito è libero dal contesto: il linguaggio L(G) è infatti razionale per qualunque presentazione. Un importante teorema dovuto a David E. Muller e Paul E. Schupp afferma che un gruppo è libero dal contesto se e solo se è libero-per-finito (un'estensione di un gruppo libero per un gruppo finito).

Sistemi di riscrittura. Molti sistemi computazionali, in particolare quelli che trattano di gruppi, fanno uso di sistemi di riscrittura per ottenere la forma ridotta degli elementi. Per esempio, il procedimento di riduzione di una parola su a_i e a__i alla corrispondente forma ridotta nel gruppo libero sui simboli a__i si può realizzare applicando le regole di riduzione a_ia__i→ε, a__ia_i→ε. L'unicità della parola ridotta esprime la proprietà di confluenza del sistema di riscrittura, vale a dire che esso fornisce un risultato indipendente dal modo in cui le regole sono applicate. Le cose vanno diversamente se le regole sono del tipo aa→ε, bb→ε, ab→c; in questo caso infatti da aab si possono derivare sia b sia ac. Una coppia come la (b, ac), che consta di due parole irriducibili derivate dalla stessa parola, si definisce critica. Esiste un algoritmo, dovuto a Donald E. Knuth e Peter B. Bendix, che permette di completare un sistema di riscrittura e trasformarlo in uno confluente senza alterare la relazione di equivalenza: esso cerca le coppie critiche e le aggiunge, con un opportuno orientamento, alle regole di riduzione. Nell'esempio precedente, aggiungendo le coppie ac→b e cb→a si ottiene un sistema confluente per un gruppo libero dal contesto.

Una teoria algebrica. È possibile dare una definizione interamente algebrica dei linguaggi liberi dal contesto, che si basa sull'idea che le grammatiche possono essere considerate come un sistema di equazioni. La caratterizzazione fa uso del quoziente sinistro di un linguaggio X per una parola u, definito come u^−1={v∣uv∈X}. Questi insiemi si possono usare per caratterizzare i linguaggi razionali: un linguaggio è razionale se e solo se l'insieme dei suoi quozienti sinistri è finito. Una famiglia F di sottoinsiemi di A* si dice stabile se u⁻¹∈F per u∈A* e X∈F. Si possono caratterizzare i linguaggi liberi dal contesto su A come gli elementi di una sottoalgebra finitamente generata dell'algebra dei sottoinsiemi di A*. Per esempio, il linguaggio di Lukasiewicz L sull'alfabeto {a,b} soddisfa l'equazione L=b+aLL. Così gli insiemi a⁻¹=L2 e b−1=ε appartengono all'algebra generata da L.

Computabilità

Riguardo alla classe più grande contenente tutti i linguaggi riconoscibili da macchine, vi sono almeno due modi di affrontarne lo studio: uno mediante un modello di macchina, la cosiddetta macchina di Turing; l'altro mediante una classe di funzioni, quelle ricorsive. Questo aspetto era presente anche nel caso dei linguaggi razionali e liberi dal contesto: nel primo caso avevamo automi finiti ed espressioni razionali, nel secondo automi a pila e grammatiche.

Macchine di Turing

Una macchina di Turing opera mediante una memoria infinita (in realtà è sufficiente una parola su un alfabeto fissato, detto nastro) sulla quale si può leggere e scrivere; ha inoltre un insieme finito di stati. Si dice che riconosce la parola w assegnata come ingresso se lo stato nel quale si ferma è uno stato finale, ma è importante osservare che può anche non fermarsi mai. Un linguaggio L riconosciuto da una macchina di Turing si dice ricorsivamente enumerabile; se è ricorsivamente enumerabile anche il suo complementare, il linguaggio prende il nome di ricorsivamente computabile (o semplicemente computabile, ovvero decidibile). In modo equivalente, L è computabile se è riconosciuto da una macchina di Turing che si ferma sempre. Un tipico linguaggio indecidibile è l'insieme delle coppie (〈M〉, x), dove M è una macchina di Turing, opportunamente codificata da una parola, e x è una parola tale che M si ferma se ha x come ingresso.

Ricorsività

Le funzioni ricorsive si possono definire come funzioni sulle parole, ma è più semplice definirle sugli interi come funzioni numeriche f(x₁,x₂,…,x_p) di p variabili intere a valori interi (gli interi si possono codificare con parole, e viceversa). La classe delle funzioni ricorsive comprende le funzioni che si possono ottenere da quelle iniziali (proiezione, successore e costanti) mediante le seguenti operazioni: (a) composizione; (b) ricorsione primitiva; (c) minimizzazione. La ricorsione primitiva permette di costruire una funzione f a partire da funzioni g, h mediante f(0, x)=g(x) e f(k+1,x)=h(f(k,x),k,x); la minimizzazione consente di costruire, da una funzione g, una funzione f tale che f(x) è il minimo intero m per il quale g(x,m)=0. È un risultato classico che le funzioni ricorsive e le macchine di Turing, come pure molti altri formalismi, definiscano le stesse classi di oggetti computabili. Secondo la cosiddetta tesi di Church, esse corrispondono a ciò che si intende per computabile. Questa nozione di computabilità non tiene conto ovviamente del tempo e dello spazio necessari a effettuare il calcolo, e in questo senso non è realistica.

Classi di complessità

La classe dei linguaggi ricorsivi contiene sottoclassi naturali definite in base alle risorse necessarie per riconoscere una parola di lunghezza n. Le restrizioni possono riguardare sia lo spazio sia il tempo impiegato dalla macchina. Una classe importante è la classe P dei linguaggi (o algoritmi) polinomiali: il tempo impiegato per una computazione da una macchina di Turing deterministica è maggiorato da una funzione polinomiale. Un'altra classe rilevante è la NP, definita come la P, ma che ammette anche macchine di Turing non deterministiche. Si ha così che un linguaggio è in NP se esiste una ricerca in un albero binario di altezza polinomiale che fornisce il risultato. Un tipico problema della classe NP è la soddisfacibilità delle formule booleane, che sono del tipo

[1] (x ∨ ⌝ y) ∧ (⌝ x ∨ z) ∧…

comprendono connettivi booleani e la negazione con le variabili x, y,… Per ogni scelta dei valori {vero, falso} per le variabili, è facile verificare se la formula è vera o falsa. Ne segue che il problema di trovare un insieme di valori per i quali la formula è valida è in NP. Si può anche dimostrare che si tratta di un problema NP-completo, nel senso che ogni problema in NP si può ridurre a questo in un tempo polinomiale. Ovviamente P⊂NP; è ragionevole supporre che P≠NP, ma ciò non è stato ancora dimostrato e anzi costituisce uno dei problemi centrali della teoria computazionale. Per citare una classe definita da restrizioni sullo spazio, la classe PSPAZIO è la classe dei linguaggi riconosciuti da una macchina di Turing che lavora in uno spazio di dimensione maggiorata da un polinomio nella lunghezza dell'ingresso. Si ha NP⊂PSPAZIO. Un tipico problema della classe PSPAZIO è la soddisfacibilità delle formule booleane con quantificatori, per esempio:

[2] ∀ x ∀ y(x ∧ ⌝ y ∨ ∃z((x ∧ z) ∨ (y ∧ z))).

Un recente risultato caratterizza la classe PSPAZIO in termini di dimostrazioni interattive, una sorta di dialogo socratico in forma moderna, che fa uso della nozione di macchina di Turing probabilistica nella quale le transizioni avvengono in modo casuale: l'accettazione di un dato ingresso x è sostituita dalla probabilità che x sia accettato. Vi sono due macchine di Turing, il dimostratore e il verificatore, e l'ingresso è un enunciato da dimostrare. Le due macchine comunicano a ogni passo e il numero dei passi è limitato da un polinomio. Un linguaggio L è in IP (interattivo polinomiale) se esiste una macchina di Turing probabilistica V (il verificatore) che lavora in tempo polinomiale e tale che x∈L se e solo se esiste una macchina di Turing D (il dimostratore) tale che x è accettato dalla coppia (D,V) con probabilità maggiore di 1−ε, per qualche ε〈1/2. Un esempio di problema della classe IP è quello del non-isomorfismo dei grafi. Il verificatore sceglie a caso un indice i∈{1,2} e una permutazione π, e invia al dimostratore il grafo H=π(G_i). Il verificatore trova j∈{1,2} tale che G_j e H sono isomorfi e accetta se i=j. Joseph Shamir ha dimostrato che si ha IP=PSPAZIO.

Teoria computazionale quantistica

La teoria computazionale quantistica nasce da un suggerimento del fisico Richard Feynman, secondo il quale la macchina di Turing può non essere in generale il modello adatto per simulare un sistema fisico quantistico. Gli inizi della teoria risalgono in generale agli anni Novanta, ma più in particolare a David Deutsch. Il criterio guida è di far uso di uno spazio degli stati rappresentato da uno spazio vettoriale di dimensione finita sul campo dei numeri complessi; le transizioni sono trasformazioni unitarie di tale spazio. Uno stato quantistico è un vettore di norma 1, in modo che le norme delle coordinate si possano interpretare come la probabilità di trovarsi in un dato stato ordinario. Per esempio, la trasformazione associata alla matrice ortogonale

[3] formula

trasforma il vettore [1,0] (interpretato come un bit che vale 0 con probabilità 1) nel vettore [1√2,1√2] (dove il bit ha la stessa probabilità di assumere uno dei due valori 0 o 1). Il risultato più importante, dovuto a Peter W. Shor, afferma che la fattorizzazione di un intero è polinomiale nel senso della complessità quantistica; si pensa che non appartenga alla classe P della complessità ordinaria.

Complessità di un circuito

fig. 3

Il calcolo del valore di una funzione booleana di n variabili dà luogo a un circuito: si tratta semplicemente di un grafo orientato aciclico, con 2n nodi sorgente, nel quale ciascun nodo è una funzione OR o una funzione AND (fig. 3). Un tale circuito riconosce un insieme di parole in {0,1}ⁿ, e precisamente quelle che corrispondono al valore 1 della funzione. Denotiamo con AC⁰ la classe dei linguaggi riconosciuti, per ciascuna lunghezza n, da circuiti di dimensione limitata da un polinomio in n e profondità limitata da una costante. La classe più ristretta NC¹ è costituita dai linguaggi riconosciuti da circuiti nei quali la profondità, invece che costante, può essere logaritmica, ma il grado entrante di ciascuna porta AND oppure OR è 2. Si ha AC⁰⊂NC¹. È stato dimostrato che l'inclusione è propria: la funzione parità, che ovviamente è in NC¹, non sta in AC⁰. Ulteriori lavori, iniziati da David A. Barrington e Denis Therien, hanno dimostrato che vi è un legame tra la complessità di un circuito e le varietà di semigruppi. In particolare, il fatto che la funzione parità non appartenga a AC⁰ è una conseguenza del fatto che i linguaggi razionali di AC⁰ sono quelli star-free.

Serie formali

Invece di trattare semplicemente insiemi di parole, è naturale considerare, dal punto di vista matematico, funzioni che dall'insieme delle parole conducano a valori in un insieme di numeri. L'interpretazione di una parola su 0 e 1 come sviluppo di un intero in base 2 è un esempio di funzione di questo tipo. Essa si può calcolare come l'elemento in alto a destra della matrice ottenuta con la sostituzione:

[4] formula

Questa impostazione permette di considerare importanti nozioni, come quella di molteplicità, quando i valori sono numeri interi, e quella di probabilità, quando i valori sono numeri reali.

Serie razionali

Queste funzioni, formalmente, sono spesso chiamate serie formali e denotate come somma

[5] ∑(S,w)w

di parole w con un coefficiente (S,w). Una serie su un alfabeto A si dice razionale se esiste un morfismo μ da A* nel monoide delle matrici n×n tale che (S,w)=λμ(w)γ per opportuni vettori λ e γ. Questa impostazione algebrica ha il vantaggio di permettere una semplificazione di molti concetti. I linguaggi razionali corrispondono così a soluzioni di sistemi di equazioni lineari. Per esempio, il linguaggio razionale X=(ab+b)* è la soluzione dell'equazione X=(ab+b)X+1. La serie generatrice f(z)=∑_nf_nzⁿ del numero di parole di lunghezza n in X è allora la frazione razionale:

[6] formula

Serie algebriche

Analogamente, i linguaggi liberi dal contesto corrispondono a soluzioni di equazioni algebriche. Per esempio, il linguaggio di Dyck generato dalla grammatica D→aDbD∣ε è semplicemente la soluzione dell'equazione D=aDbD+1. Di conseguenza la serie generatrice d(z)=∑_nd_nzⁿ del numero d_n di parole di lunghezza n in D è la serie:

[7] formula

soluzione dell'equazione z^{2(z)2−d(z)+1=0.} Le serie formali hanno trovato importanti applicazioni nell'analisi degli algoritmi e nella combinatoria enumerativa.

Combinatoria delle parole

I problemi combinatori che riguardano parole sono stati studiati molto presto; i lavori di Thue segnano un momento storico. Il risultato più classico, dovuto originariamente a Thue e dimostrato più volte in seguito, è l'esistenza di parole infinite prive di quadrati, là dove in una parola un quadrato è un fattore ripetuto, della forma ww. Il modo più semplice di ottenere una parola priva di quadrati è il seguente. Si prenda la parola di Thue-Morse

[8] t = abbabaab…

definita come segue: sia β(n) il numero di 1 nello sviluppo binario di n, allora t_n=a se β(n) è pari e t_n=b se è dispari. Si formi quindi la parola

[9] m = abcacbabcbac…

controimmagine di t nella sostituzione seguente:

[10] a→abb, b→ab, c→a.

Si può allora dimostrare che m è priva di quadrati. La parola di Thue-Morse non è ovviamente priva di quadrati, in quanto è definita su un alfabeto binario e ogni parola binaria abbastanza lunga ha un quadrato. Tuttavia è priva di cubi, né contiene sovrapposizioni, ossia fattori della forma uvuvu con u non vuota.

Parole sturmiane

Le parole sturmiane hanno una lunga storia, che risale al matematico e astronomo Johann Bernoulli III. Una loro definizione equivalente è quella di una parola infinita x tale che per ogni n il numero p(n) di blocchi distinti di lunghezza n che vi compaiono è n+1; si può dimostrare che se p(n)≤n, allora è una costante, e la parola x è definitivamente periodica. L'esempio più semplice di parola sturmiana è la parola di Fibonacci:

[11] f = 01001010…

che è il punto fisso della sostituzione 0→01, 1→0. Vi sono tre fattori di lunghezza 2, che sono 00, 01 e 10, e quattro fattori di lunghezza 3, ossia 001, 010, 100 e 101. Si ha anche un'altra definizione della parola di Fibonacci, che fa riferimento ad approssimazioni di irrazionali mediante razionali. Sia infatti s la successione:

[12] formula

fig. 4

dove α=1/φ² con φ=(1+√5)/2 e dove ∧x≠ è il massimo intero contenuto in x. Si ha allora s=0f. Questa formula mostra che i simboli f_n si possono interpretare come l'approssimazione di una retta di pendenza α, che abbia punti con coordinate intere (fig. 4). Per un teorema di Morse e Hedlund, le parole sturmiane si possono anche definire come quelle che hanno n+1 fattori di lunghezza n, o anche per mezzo di una formula come la [12], in cui α sia un numero irrazionale.

Equazioni in parole

Le equazioni in parole costituiscono un attivo campo di ricerca. Una tale equazione è semplicemente una coppia x=y di due parole su un alfabeto A∪X di costanti da A e incognite da X. Una soluzione è una sostituzione di una parola su A per ciascuna delle incognite x∈X. Per esempio, l'equazione ax=yb ha la soluzione x=b, y=a. Gennady S. Makanin ha dimostrato per primo che l'esistenza di una soluzione è un problema decidibile.

Applicazioni

Menzioniamo brevemente alcune applicazioni pratiche delle nozioni e dei metodi che abbiamo descritto.

Compilatori. La possibilità di compilare in modo efficiente un linguaggio di programmazione di alto livello si può considerare uno dei grandi successi nella storia dell'informatica. Da quando, negli anni Cinquanta del Novecento, Backus scrisse il primo compilatore Fortran, sono stati ideati centinaia di linguaggi di programmazione; scrivere un compilatore fa parte del lavoro di processare un linguaggio. Il legame con i linguaggi formali è per grandi linee il seguente. La parte lessicale di un compilatore che tratta nozioni di basso livello, come il format dell'ingresso, è descritta da automi finiti. Esistono molti strumenti di software per facilitare l'implementazione di questa parte, che va sotto il nome di analisi lessicale. La sintassi di un linguaggio di programmazione, inoltre, è generalmente descritta per mezzo di una grammatica libera dal contesto, o di un formalismo equivalente. Il procedimento che controlla la correttezza sintattica (e che computa la struttura sintattica) è noto come analisi sintattica e si effettua con metodi che implementano una forma di automa a pila. La traduzione dal linguaggio sorgente al linguaggio oggetto (linguaggio macchina di basso livello) costituisce la terza parte, che implementa l'attraversamento di un albero che può essere descritto da una grammatica ad attributi. La possibilità di far uso dei metodi della teoria dei linguaggi formali per costruire compilatori è considerata qualcosa di straordinario.

Trattamento di testi. Il trattamento dei testi comporta problemi di livello relativamente modesto ed è importante per la vita di ogni giorno: comprende l'uso dei processori di parole per un pubblico generale, ma anche tecniche più complicate per produrre testi stampati di alta qualità. Un campo di ricerca molto attivo è quello degli algoritmi di confronto di schemi (pattern matching). Il più famoso è l'algoritmo di Donald E. Knuth, James H. Morris e Vaughan R. Pratt, che permette di localizzare una parola w in un testo t in un tempo proporzionale alla somma delle lunghezze di w e t, piuttosto che al loro prodotto come nell'algoritmo ingenuo che cerca tutte le possibili posizioni di w in t. Questo algoritmo è strettamente legato al calcolo dell'automa minimo che riconosce l'insieme delle parole che terminano con w. Esistono poi numerosi algoritmi di compressione, processo importante ai fini di velocizzare la trasmissione dei testi e ridurre la loro dimensione, e molti di essi si basano su idee che rientrano nel campo degli automi finiti e dei linguaggi formali. Uno dei più famosi è il metodo di Ziv-Lempel, che fattorizza l'ingresso in blocchi x_12…xn…, dove è la parola più corta tra quelle che non si trovano nella sequenza (x1,x2,…,xn).

Linguaggi naturali. Automi e grammatiche sono stati usati fin dall'inizio per il processing di linguaggi naturali. Gli automi finiti sono largamente applicati, spesso con il nome di reti di transizione, alla descrizione di fenomeni di fonetica e di lessicografia o per la descrizione di frasi elementari. L'uso di grammatiche permette di trattare strutture nidificate come quelle generate da clausole subordinate.

Genomi. I progressi della biologia molecolare, e in particolare la scoperta del codice genetico, hanno inaugurato la biologia computazionale, che tratta sequenze di significato biologico come oggetti computazionali. Nell'analisi di queste sequenze sono stati applicati numerosi algoritmi, alcuni elaborati appositamente. Uno dei più famosi, dovuto originariamente a Daniel S. Hirschberg e riscoperto da vari autori, è il confronto tra sequenze (string matching) basato su una tecnica, detta di programmazione dinamica, che ricerca la più lunga sottosequenza comune a due sequenze in un tempo proporzionale al prodotto delle loro lunghezze.

Bibliografia

Backus 1959: Backus, John W., The syntax and semantics of the proposed international algebraic language of the Zürich ACM-GAMM conference, in: Proceedings of the International conference on information processing, Paris, UNESCO, 1959, pp. 125-132.

Berstel, Perrin 1985: Berstel, Jean - Perrin, Dominique, Theory of codes, New York, Academic Press, 1985.

Book, Otto 1993: Book, Ronald - Otto, Friedrich, String-rewriting systems, New York, Springer, 1993.

Chomsky 1956: Chomsky, Noam, Three models for the description of language, "IRE transactions on information theory IT-2", 3, 1956, pp. 113-124.

Deutsch 1985: Deutsch, David, Quantum theory, the Church-Turing principle and the universal quantum computer, "Proceedings of the Royal Society of London A", 400, 1985, pp. 97-117.

Eilenberg 1974-1976: Eilenberg, Samuel, Automata, languages and machines, New York-London, Academic Press, 1974-1976, 2 v.

Epstein 1992: Epstein, David B.A. e altri, Word processing in groups, Boston (Mass.), Jones and Bartlett, 1992.

Feynman 1982: Feynman, Richard, Simulating physics with computers, "International journal of theoretical physics", 21, 1982, pp. 467-488.

Gusfield 1997: Gusfield, Dan, Algorithms on strings, trees, and sequences, Cambridge, Cambridge University Press, 1997.

Harris 1946: Harris, Zelig, From morpheme to utterance, "Language", 22, 1946, pp. 161-183.

Hashiguchi 1987: Hashiguchi, Kosaburo, Algorithms for determining relative star height and star lighting, "Information and computation", 78, 1987, pp. 124-169.

Kleene 1956: Kleene, Stephen C., Representation of events in nerve nets and finite automata, in: Automata studies, edited by Claude E. Shannon and John McCarthy, Princeton (N.J.), Princeton University Press, 1956, pp. 3-42.

Krohn, Rhodes 1965: Krohn, Kenneth - Rhodes, John L., Algebraic theory of machines, I. Prime decomposition theorem for finite semigroups and machines, "Transactions of the American Mathematical Society", 116, 1965, pp. 450-464.

Lind, Marcus 1996: Lind, Douglas - Marcus, Brian, Symbolic dynamics and coding, Cambridge, Cambridge University Press, 1996.

Lothaire 2002: Lothaire, M., Algebraic combinatorics on words, Cambridge, Cambridge University Press, 2002.

Lothaire 2003: Lothaire, M., Applied combinatorics on words, Cambridge, Cambridge University Press, 2003.

McCulloch, Pitts 1943: McCulloch, Warren - Pitts, Walter, A logical calculus of the ideas immanent in nervous activity, "Bulletin of mathematical biophysics", 5, 1943, pp. 115-133.

McNaughton, Papert 1971: McNaughton, Robert - Papert, Seymour, Counter-free automata, Cambridge (Mass.), MIT Press, 1971.

Post 1936: Post, Emil L., Finite combinatory processes - formulation 1, "Journal of symbolic logic", 1, 1936, pp. 103-105.

Roche, Schabes 1997: Roche, Emmanuel - Schabes, Yves, Finite-state language processing, Cambridge (Mass.), MIT Press, 1997.

Sedgewick, Flajolet 1996: Sedgewick, Robert - Flajolet, Philippe, Analysis of algorithms, Reading (Mass.), Addison-Wesley, 1996.

Sénizergues 1997: Sénizergues, Géraud, The equivalence problem for deterministic pushdown automata is decidable, "Lecture notes in computer science", 1256, 1997, pp. 671-681.

Sénizergues 2002: Sénizergues, Géraud, L(A)=L(B)? A simplified decidability proof, "Theoretical computer science", 281, 2002, pp. 555-608.

Shor 1997: Shor, Peter W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, "SIAM journal on computing", 26, 1997, pp. 1484-1509.

Sims 1994: Sims, Charles, Computation with finitely presented groups, in: Encyclopedia of mathematics and its applications, Cambridge, Cambridge University Press, XLVIII, 1994.

Straubing 1994: Straubing, Howard, Finite automata, formal logic, and circuit complexity, Boston, Birkhäuser, 1994.

Thue 1906: Thue, Axel, Über unendliche Zeichenreihen, "Norske Videnskabers Selskabs skrifter I, Matematisk-Naturvidenskapelig Klasse", 7, 1906, pp. 1-22.

Turing 1936-1937: Turing, Alan M., On computable numbers with an application to the Entscheidungsproblem, "Proceedings of the London Mathematical Society", 42, 1936-1937, pp. 230-265.

Waterman 1995: Waterman, Michael S., Introduction to computational biology, London, Chapman and Hall, 1995.