INFORMATICA

INFORMATICA

Con il termine informatica, neologismo di origine francese, s'indica attualmente una nuova ed emergente disciplina, la quale si occupa di particolari rappresentazioni di oggetti concreti o astratti, di fenomeni, di processi, di fatti, di idee, ecc. e delle operazioni eseguibili su esse. Queste rappresentazioni sono chiamate "dati" (usando tale termine in una accezione nuova, ma ormai diffusa in molte lingue) e sono particolari in quanto sono definibili in modo formale e sono capaci di essere trattate da macchine particolari dette elaboratori elettronici (v. in questa App.), di essere trasmesse (per es., per mezzo di segnali elettrici) e di essere anche interpretabili dall'uomo.

Un dato è, per es., centoventitre, un altro è 123. Entrambi hanno lo stesso significato anche se il primo è composto di una successione di lettere e l'altro di una successione di cifre; entrambi infatti rappresentano uno stesso ente astratto: il "numero centoventitre", che è pure rappresentabile con CXXIII.

Fra le tre rappresentazioni di tale numero, quella fatta con le lettere può essere preferibile, per es., nel testo di un telegramma perché più difficilmente alterabile a causa di errori nella trasmissione, però la rappresentazione fatta con cifre decimali è la più conveniente nel caso di operazioni aritmetiche perché l'aritmetica elementare ci fornisce poche e semplici regole per passare dalla rappresentazione degli operandi a quella del risultato. Tale passaggio è più difficile nel caso della rappresentazione romana dei numeri ed è ancora più complicato nel caso della rappresentazione per esteso (come "centoventitre"), che, inoltre, varia da lingua a lingua.

L'i. però non si occupa solo dei numerali, cioè delle rappresentazioni dei numeri, ma anche di altre rappresentazioni (per es., di testi composti con caratteri di un certo alfabeto, di elettrocardiogrammi, di fotografie, ecc.) per le applicazioni più svariate.

Applicazioni che, per es., potranno consistere corrispondentemente: nella registrazione di un testo e nel suo successivo reperimento da un insieme di registrazioni di molti altri testi in base al suo titolo o, addirittura in base al suo contenuto; nell'analisi automatica di un elettrocardiogramma eseguita da un elaboratore elettronico allo scopo di segnalare a un cardiologo eventuali anomalie; nell'analisi di fotografie aree per la rivelazione di incendi o malattie epidemiche in boschi di zone vaste e poco accessibili.

Altre applicazioni più comuni riguarderanno dati rappresentanti numeri o grandezze fisiche per calcoli tecnici e scientifici, oppure riguarderanno dati rappresentanti denaro, quantità di materie prime, di semilavorati, di prodotti finiti, ecc., per applicazioni di tipo bancario, amministrativo, per il controllo di processi produttivi attuati mediante impianti a produzione continua o mediante linee di montaggio, ecc.

Per ogni tipo di dato si definisce un dominio, cioè un insieme di valori che possono essere assunti dai dati di quel certo tipo (per es.: gl'interi da 0 a 10¹⁰, oppure i caratteri dell'alfabeto di una telescrivente) e delle relazioni od operazioni fra elementi del dominio.

Per es., nel caso degl'interi suddetti si potranno definire delle operazioni di tipo aritmetico, naturalmente tenendo conto del fatto che il dominio di definizione dei dati è finito. Viceversa, nel caso dei caratteri si potranno definire operazioni quali la giustapposizione di caratteri e di successioni di caratteri, per cui dati due caratteri alfabetici, per es., S ed E, si forma per giustapposizione la successione SE, oppure date due successioni di caratteri X3VA e KB si forma la successione X3VAKB.

Nel caso di dati che possono considerarsi composti da altri dati considerati elementari (per es., una successione di caratteri oppure una matrice di dati rappresentanti ognuno un numero intero) si hanno delle relazioni fra i dati elementari (per es., una relazione d'ordinamento totale fra gli elementi di una successione) che possono corrispondere a relazioni fra gli enti rappresentati da ciascun dato elementare o a relazioni di accesso fra tali dati, eventualmente registrati in una memoria di un elaboratore elettronico.

Un dominio di dati e le relative relazioni e operazioni costituiscono ciò che attualmente si chiama una "struttura di dati".

Non possiamo qui addentrarci in formalizzazioni di tale concetto che è stato qui delineato in modo del tutto discorsivo, però è interessante notare che a classi di problemi si possono da un lato far corrispondere certe strutture algebriche quando i problemi stessi siano trattati a livello di astrazione matematica e dall'altro certe strutture di dati quando, invece, i problemi siano trattati dal punto di vista della loro soluzione con un elaboratore elettronico.

In genere gli elaboratori elettronici hanno solo pochi tipi primitivi di strutture di dati: bit, cioè cifre binarie, caratteri e numerali (rappresentati a loro volta da sequenze di bit) con poche operazioni fondamentali o primitive su esse, specificabili con istruzioni, con le quali si possono formare dei programmi.

Altri tipi di strutture di dati devono essere realizzati su un elaboratore mediante quelle primitive, e in effetti anche queste vengono realizzate nell'elaboratore mediante strutture più semplici, riducibili al dominio formato dalle cifre binarie 0 e 1 e alle operazioni su di esse. Tali operazioni appartengono a un'algebra particolare, detta algebra di Boole, dal nome del suo creatore, e definita sul dominio suddetto.

Ogni volta che ci sia da realizzare una struttura di dati non primitiva con strutture primitive si procede a rappresentare gli elementi del dominio da realizzare con elementi del dominio della struttura primitiva e le operazioni relative con sequenze di operazioni primitive, sequenze sinteticamente espresse da programmi redatti usando appositi linguaggi programmativi (cioè linguaggi adatti a esprimere programmi).

Così, per es., nell'aritmetica decimale si rappresentano i numeri interi con sequenze di dati primitivi che sono le cifre decimali. Le operazioni fra numeri interi sono realizzate con procedure che usano come operazioni primitive quelle fra singole cifre decimali, descritte dalla tavola pitagorica e dalle altre che sono oggetto di studio nei primi anni di scuola.

Quando perciò si sono individuate certe strutture di dati atte a risolvere certe classi di problemi, per poterle realizzare su un certo elaboratore sarà necessario esprimerle mediante le strutture primitive di questo, redigendo allo scopo appositi programmi scritti nel linguaggio programmativo proprio dell'elaboratore stesso.

Quando una classe di problemi si presenta frequentemente può essere conveniente ipotizzare un elaboratore astratto che ammetta come primitive le strutture di dati più convenienti per la risoluzione di tali problemi e scrivere i programmi risolutivi nel linguaggio proprio di tale ipotetico elaboratore.

Tali programmi dovranno essere poi tradotti (da apposito programma traduttore) in programmi scritti nel linguaggio programmativo di un elaboratore effettivamente disponibile.

Non è possibile addentrarci ulteriormente nei problemi relativi alle metodologie di programmazione, tuttavia è opportuno aggiungere qualche notizia sui risultati teorici acquisiti sui linguaggi programmativi i quali possono considerarsi un caso particolare dei linguaggi definiti formalmente, cioè linguaggi formali.

Questi sono definiti da un insieme di simboli (detto alfabeto), da un insieme di regole (detto grammatica o sintassi) per formare le parole e le frasi del linguaggio, da un insieme di regole (detto semantica) per associare a ciascuna frase un significato, in genere per composizione dei significati dei componenti sintattici della frase.

Alla teoria dei linguaggi si collega la teoria degli automi, a sua volta collegata con la teoria della commutazione (ingl.: switching theory) e con quella della computabilità.

Qui accenneremo solo al fatto che un "automa" può essere definito come un sistema capace di operare su successioni (anche infinite) di caratteri di un alfabeto trasformandole in altre successioni dello stesso alfabeto. Un automa è schematizzabile come uno (o più) nastri composti di celle nelle quali un apposito organo di controllo può scrivere un carattere o leggere un carattere.

L'organo di controllo può anche muovere il nastro o i nastri in modo da operare su qualunque cella di esso, e ciò in funzione di quello che legge sul nastro stesso, che costituisce perciò una sorta di memoria dell'automa analoga alla memoria d'un elaboratore elettronico, di cui l'automa costituisce un modello assai semplice.

Tale modello però lo si può mettere a base della teoria della computabilità che si occupa di stabilire quali funzioni possono essere calcolate da un automa o in generale da un elaboratore.

La teoria della commutazione si occupa invece dei sistemi aventi un numero finito di stati interni, di stati d'ingresso e di stati di uscita. Poiché a una sequenza di stati in ingresso o in uscita si può far corrispondere una sequenza di caratteri su un nastro d'un automa, è ovvio il collegamento fra la teoria degli automi e quella della commutazione.

Quest'ultima, però, è essenzialmente volta all'analisi e alla sintesi dei dispositivi e delle reti di dispositivi a piccolo numero di stati e ha perciò diretta connessione con la progettazione dei circuiti relativi (spesso detti circuiti digitali) usati per la costruzione degli elaboratori elettronici.

Altri capitoli recenti dell'i. riguardano la semantica dei linguaggi, la teoria dei programmi e degli schemi di programmi, la teoria della complessità degli algoritmi.

Rapporti notevoli per gli aspetti teorici, pratici, applicativi o costruttivi dell'i. esistono fra questa e logica, algebra astratta, analisi numerica, teoria dei sistemi, teoria dei controlli e automazione, teoria dell'ottimizzazione, cibernetica, ricerca operativa, elettronica, metodologie di controllo gestionale e di controllo contabile, linguistica, documentazione, ecc.

Un'ultima questione riguarda l'uso particolare e spesso ambiguo che del termine informazione si fa in informatica. Talora infatti viene usato come sinonimo di ciò che abbiamo definito come dato, sebbene in genere per "informazione" si intenda invece in i. "il significato che l'uomo assegna ai dati per mezzo di convenzioni note" (definizione dell'IFIP, International association For Information Processing, il più autorevole organismo culturale su base internazionale nel campo dell'informatica). Tale definizione, che si riallaccia alle idee di Carnap e della sua scuola, rende l'informazione di un dato dipendente da chi la interpreta e perciò relativa.

Nella teoria dell'informazione (v. App. III, 11, p. 874), che deriva dai lavori di C. E. Shannon sulle comunicazioni elettriche, si definisce come quantità d'informazione una grandezza fisica misurabile, definita su base probabilistica e collegabile al concetto di entropia.

È però da notare che più recentemente si sono proposte delle definizioni di quantità d'informazione basate sul concetto di complessità degli algoritmi (quelli di riconoscimento del segnale) e perciò rientranti per questo aspetto nell'ambito dell'informatica.

Implicazioni economiche e sociali dell'informatica.- In poco più di vent'anni l'industria dei calcolatori elettronici è divenuta uno dei pilastri della economia dei paesi più avanzati.

Nel 1975 la maggiore industria del settore, l'IBM, è la settima impresa industriale statunitense in termini di fatturato e la seconda in termini di profitti. Un ritmo di rinnovamento tecnologico di 4 ÷ 5 anni, le spese di ricerca, di progettazione, di vendita, di assistenza ai clienti, di riaddestramento del personale hanno portato alla concentrazione di tale industria in poche aziende multinazionali, debolmente contrastate da compagnie giapponesi o europee.

Ciò ha creato il timore che l'industria dei calcolatori, e di conseguenza quella elettronica, restino appannaggio di pochissimi paesi, almeno per quanto riguarda la ricerca, il progetto e la pianificazione dei prodotti.

D'altra parte anche negli SUA la potenza delle multinazionali, la loro relativa indipendenza dai vari governi nazionali e perciò la posizione di oligopolio se non di monopolio di tali industrie ha sollevato seri interrogativi.

Tenendo conto che l'elaboratore elettronico è di fatto divenuto non solo un elemento di base dello sviluppo scientifico, militare, industriale, ma anche un insostituibile strumento per la gestione amministrativa di gran parte delle attività di un paese moderno, si vede come certi timori e certi discorsi possono non essere infondati.

È da notare inoltre che il peso economico dell'i. non si esplica solo attraverso la produzione degli elaboratori, ma anche (e in misura sempre maggiore e ormai prevalente) nelle attività connesse con l'analisi dei problemi, la redazione dei programmi, il loro aggiornamento, l'addestramento del personale, ecc.

I progressi delle tecniche di elaborazione a distanza mediante terminali del tipo video, la diffusione di linguaggi e tecniche che rendono assai semplice accedere a grossi archivi o banche di dati, fanno sì che l'elaboratore non sia più confinato in un centro di calcolo, ma s'irradi nei vari reparti delle fahbriche, nei magazzini, negli uffici, agli sportelli per il pubblico di servizi di vario genere.

Inoltre i progressi della microelettronica, che portano verso i microcalcolatori, cioè verso elaboratori di potenzialità già apprezzabile ma delle dimensioni di una moneta e del costo (1975) di alcune centinaia di migliaia di lire, fanno sì che il calcolatore tenda a divenire un componente elettronico intelligente: cioè dotato di memoria e programmabile. Di qui la tendenza a ulteriori vasti impieghi per una gran quantità di applicazioni.

Da ciò discendono grossi problemi di acculturazione, di formazione professionale, di addestramento specialistico, di aggiomamento, di mutamenti organizzativi e normativi, di scontro con legislazioni sorpassate, di mobilità del personale, di garanzia del posto di lavoro, d'impostazione della formazione tecnica su base sistemistica anziché tecnologica, di professionalità, ecc.

Sorgono inoltre altri problemi riguardanti il diritto del cittadino di sapere quali dati che lo concernono vengono registrati su calcolatore e da chi e di controllare l'accesso a tali dati da parte di terzi.

Sorgono anche timori che gli elaboratori possano portare a strutture sociali di tipo autoritario, come sorgono sospetti di un consumismo snobistico anche nel campo degli elaboratori.

Di queste problematiche, come delle precedenti che consideravano gli aspetti tecnici e scientifici dell'i. come disciplina, qui abbiamo dato solo degli accenni.

Bibl.: M. L. Minsky, Computation: finite and infinite machines, Londra 1967; F. Luccio, Strutture linguaggi sintassi, Torino 1972; R. Rustin, Formal semantics of programming languages, Londra 1972; Italiani, Serazzi, Elementi di informatica, Milano 1973; C. C. Gottlieb, A. Borodin, Social issues in computing, New York 1973; Autori vari, Razionalità sociale e tecnologia della informazione, Milano 1973; Autori vari, I problemi dell'informatica, in Ambiente e informatica: problemi nuovi della società contemporanea, Camera dei deputati, Quaderni di studi e legislazione, Roma 1974; Z. Manna, Mathematical theory of computation, New York 1974; W.S. Brainerd, L. H. Landweber, Theory of computation, ivi 1974; Hermes, Enumerabilità decidibilità computabilità, Torino 1975; V. P. Preparata, R. T. Yeh, Introduzione alle strutture discrete, ivi 1976.

Informatica matematica, teoria dei linguaggi.

I settori dell'i. con un più chiaro carattere matematico sono la teoria dei linguaggi formali e la teoria degli automi a essa strettamente collegata.

Teoria dei linguaggi formali. - La teoria dei linguaggi formali considera sequenze finite di oggetti del tutto semplici, cioè caratterizzati solo dalla loro individualità e non ulteriormente analizzabili. Tali oggetti si dicono "simboli" o "lettere" e sono rappresentati da segni grafici. Le sequenze di simboli sono chiamate "stringhe" o "parole" e si rappresentano accostando i segni grafici.

Occorre fare riferimento a determinati insiemi finiti di simboli che si dicono "alfabeti".

La giustapposizione tra stringhe, cioè il loro accostamento, è, in termini algebrici, un'operazione binaria non commutativa e associativa; l'insieme di tutte le stringhe su un alfabeto A, munito dell'operazione di giustapposizione, costituisce la struttura algebrica nota come "semigruppo libero generato da A" ed è denotato con A⁺.

È opportuno considerare anche un'unità per la giustapposizione, cioè un oggetto che indichiamo con e e diciamo "stringa vuota", la cui giustapposizione a destra o a sinistra di una qualsiasi stringa w dia la stessa w: ossia ew = we = w. Con l'aggiunta di e, A⁺ diventa un monoide detto "monoide libero generato da A" e indicato A*.

Ora, si dice "linguaggio (formale) L sull'alfabeto A" ogni sottinsieme di A*.

Sui linguaggi si definiscono varie operazioni significative per le applicazioni che è opportuno studiare in termini algebrici. Poiché i linguaggi sono degli insiemi (di stringhe), su di essi si possono considerare operazioni insiemistiche come intersezione o unione; è comodo denotare l'unione di linguaggi con i segni di somma + e Σ.

Prodotto (di giustapposizione) di due linguaggi L e M è il linguaggio L • M costituito da tutte le stringhe ottenute giustapponendo una stringa di L con una di M. Per "+-chiusura" di L, denotata con L⁺, s'intende il linguaggio costituito dalle stringhe ottenute giustapponendo un numero qualsiasi di stringhe di L, mentre la "*-chiusura di L", denotata con L*, è data da e + L⁺.

Si dice "riflessa" di una stringa w la stringa w^ρ ottenuta considerando le lettere nella w in ordine inverso; per es., con questa notazione una "palindrome" è una stringa w tale che w^ρ = w.

L'insieme dei linguaggi su un alfabeto se munito del solo prodotto costituisce un monoide; se munito di + e • costituisce un semianello, struttura che generalizza quelle di anello, nella quale il linguaggio vuoto ??? e quello costituito dalla sola e sono lo zero e l'unità.

L'insieme dei linguaggi munito di +, • e * viene studiato come struttura algebrica con il nome di "algebra classica di Kleene".

Un'importante operazione consiste nel rimpiazzare in una stringa ogni occorrenza di una lettera con una stringa o con un linguaggio: nel primo caso si ha un morfismo di monoidi in quanto per una tale trasformazione h e per due stringhe generiche h(w • z) = h(w) • h(z); la seconda trasformazione estesa ai linguaggi viene detta "sostituzione" e costituisce un morfismo di algebre di Kleene.

Esempi:

Sull'alfabeto A = {a, b} il linguaggio delle stringhe che presentano lettere a seguite da lettere b è espresso da a⁺ • b⁺; se le a e le b possono anche mancare abbiamo a* • b*; se invece s'impone che il numero delle a sia uguale a quelle delle b, si ha

Il linguaggio costituito dalle stringhe su A = {a, b, c} che presentano almeno due a o due b consecutive ma non presentano due c accostate è dato da A* (aa + bb) A* − A* ccA*.

Le scritture decimali dei numeri interi costituiscono un linguaggio sull'alfabeto {+, −, 0, 1, ..., 9}; gl'interi si possono esprimere anche con scritture binarie, cioè con stringhe su {+, −, 0, 1}; il passaggio dalla scrittura in base 4 a quella in base 2 si può vedere come morfismo di monoidi che sostituisce 0 con 00, 1 con 01, 2 con 10 e 3 con 11.

Sull'alfabeto {x, y, z, (,), +, −, • ,/, 0, 1, ..., 9} si costruisce il linguaggio delle espressioni algebriche nelle variabili x, y e z.

Più in generale, un programma in un linguaggio di programmazione (FORTRAN, COBOL,...) è dato da una stringa su un alfabeto per gli elaboratori di dati (ASCII, EBCDIC).

La codifica di un messaggio con l'alfabeto Morse si può pensare come sostituzione di lettere dell'alfabeto con sequenze di linee e punti.

Gli anagrammi di una parola sono stringhe ottenute permutando le sue lettera e un rebus si può descrivere come la giustapposizione di parole con gruppi di lettere per dare una stringa fattorizzabile in una sequenza di nuove parole costituenti una frase di senso compiuto; similmente la teoria dei linguaggi può essere usata a livello descrittivo in altri problemi di enigmistica e di criptologia.

Le parole della lingua italiana costituiscono un insieme finito ma molto ampio di stringhe sulle 21 lettere alfabetiche e sui due accenti (acuto e grave); le frasi sensate della lingua italiana si può pensare che costituiscano un linguaggio sul precedente alfabeto ampliato con i simboli di spaziatura fra parole e di apostrofo.

Costituiscono un linguaggio anche i teoremi di una teoria formalizzata: in tal caso l'alfabeto comprende lettere per variabili, costanti e segni operatoriali della teoria e segni logici; il linguaggio dei teoremi è contenuto nel linguaggio delle formule ben formate della teoria.

Come fanno intravvedere gli esempi precedenti, la teoria dei linguaggi si pone obiettivi molto ampi, come accade ad altre strutture ad assiomi deboli. In effetti, lo studio dei linguaggi è stato sviluppato in ambienti diversi e con strumenti e finalità diverse: fondamenti della matematica, linguistica, controllo, elaborazione automatica dei dati.

Un problema di base della teoria dei linguaggi è quello della "presentazione", cioè il problema delle modalità e degli strumenti mediante i quali specificare quali parole appartengono a un linguaggio. Se il linguaggio si compone di un numero finito di stringhe basterebbe un loro elenco; se però esso è molto esteso, una tale presentazione risulta onerosa e poco utile allo studio; un tale elenco può essere interessante solo se registrato e manipolato mediante un elaboratore. Se, viceversa, un linguaggio L sull'alfabeto A è infinito, come nella massima parte dei casi interessanti, è indispensabile disporre di una sua presentazione in termini finiti.

Presentazioni formalmente soddisfacenti di una classe di linguaggi ???&out;l dovrebbero essere fornite da regole espresse da stringhe su un alfabeto ???&out;a costituenti nel loro complesso un linguaggio ???&out;m; rispetto a ???&out;l, ???&out;m "viene detto "metalinguaggio" e i simboli di ???&out;a "segni metalinguistici". Oltre a ???&out;m devono essere precisate delle regole ???&out;r d'interpretazione che consentono di associare a ciascuna delle sue stringhe un ben determinato linguaggio di ???&out;l. Spesso, assegnato ???&out;m, le regole ???&out;r "s'impongono in modo naturale e possono essere lasciate implicite; in genere, poi, alle stringhe di ???&out;m si sostituisce una loro descrizione informale.

Un primo tipo di strumenti per presentare linguaggi è dato da espressioni nelle quali entrano i simboli dell'alfabeto e operazioni sui linguaggi come +, • , * e ^ρ. Questi segni vengono quindi considerati simboli metalinguistici insieme con i simboli dell'alfabeto, le parentesi e gli altri delimitatori che risulta opportuno utilizzare nelle espressioni. Si hanno metalinguaggi ???&out;m costituiti da tutte o alcune espressioni relative a un dato insieme di operatori; le regole ???&out;r dicono d'interpretare ogni stringa di ???&out;m come linguaggio su A secondo il significato degli operatori; esse naturalmente possono essere sottaciute. Il più importante esempio di collezione di linguaggi presentabili in questo modo è costituito dai linguaggi razionali o regolari, linguaggi forniti da espressioni nelle quali possono comparire gli operatori +, • e *. Le collezioni di linguaggi presentabili con la totalità delle espressioni con dati operatori sono esprimibili anche come chiusure algebriche.

Automi o macchine formali. - Un altro tipo del tutto generale di strumenti per la presentazione e lo studio dei linguaggi è dato dagli "automi" o "macchine formali". Con tali termini s'indicano genericamente vari tipi di sistemi formali che costituiscono modelli discreti più o meno completi e fedeli del comportamento di macchine e dispositivi automatici reali o realizzabili. Queste strutture hanno in comune la caratteristica di prendere in esame sequenze di comandi tendenzialmente semplici e quindi rappresentabili come stringhe, dette "stringhe di input". Quando si schematizza con una macchina formale un apparato fisico si prescinde, anche in misura molto larga, dalla sua costituzione interna e dai dispositivi materiali che lo costituiscono. Tutto questo viene rappresentato considerando che la macchina formale possa trovarsi in una collezione di situazioni con una precisa individualità e chiamate "stati interni dell'automa".

Anche l'evoluzione nel tempo è fortemente semplificata e viene descritta come una sequenza discreta di transizioni o mosse fra "configurazioni istantanee". Ogni configurazione è determinata da uno stato interno della macchina e da altre caratteristiche che dipenderanno dalla particolare struttura dell'automa. Descrivendo con una sequenza di transizioni il comportamento dell'automa non si tiene conto delle situazioni intermedie che si riscontrano per l'apparato fisico, né delle modalità e dei tempi secondo i quali si attua la modificazione; quindi si trascurano le eventualità di malfunzionamento, la possibilità che l'apparato si trovi in situazioni non perfettamente coincidenti con quelle caratterizzate dagli stati e ogni fenomeno di "rumore" (di questi fenomeni si tiene però conto nei cosiddetti automi probabilistici). L'evoluzione di un automa, quindi, è caratterizzata in particolare dalla sequenza degli stati nei quali si viene a trovare in successivi istanti. Si può introdurre una scala discreta dei tempi dell'automa t₀, t₁, ..., t_n, ... Evoluzione e scala dei tempi potrebbero aver fine o prolungarsi indefinitamente.

La stringa di input che determina l'evoluzione di un automa si può pensare registrata su un supporto sequenziale di informazioni, cioè su un dispositivo rappresentabile con una sequenza di caselle in ciascuna delle quali è registrabile un simbolo. Per analogia con i sistemi elettronici il suddetto dispositivo viene chiamato "nastro di input " e si dice che viene letto dall'automa mediante una "testina di lettura". Si può supporre che un nastro di input venga presentato all'automa all'inizio di ogni sua evoluzione e caratterizzi in modo determinante la sua configurazione iniziale.

Il tipo più semplice di macchina formale, il semiautoma, possiede un insieme finito di stati, e un nastro di input il quale viene scandito da una testina a partire dal simbolo più a sinistra della stringa e a ogni mossa legge il simbolo nella casella sulla quale si trova e si sposta su quella immediatamente a destra. La lettura del nastro procede di pari passo con l'evoluzione la quale, quindi, si conclude dopo un numero di mosse pari alla lunghezza della stringa di input.

Se si chiede che la macchina all'inizio di ogni sua evoluzione si trovi sempre in un determinato stato detto "iniziale" e se si distingue un insieme di stati detti "stati finali", si privilegiano tra le stringhe di input quelle la cui lettura porta dallo stato iniziale a uno stato finale. Il complesso di queste stringhe costituisce il cosiddetto "linguaggio riconosciuto" o "accettato" dalla macchina. Questo automa, ottenuto arricchendo un semiautoma con stati iniziali e finali, è noto come "riconoscitore a stati finiti di Rabin e Scott" e fornisce il primo esempio di presentazione di un linguaggio mediante un meccanismo in grado di distinguere con un numero finito di passi se una stringa gli appartiene o meno. Un teorema dovuto a S. C. Kleene dimostra che i linguaggi così riconosciuti sono i linguaggi razionali.

Una prima variante dei riconoscitori sopra descritti è costituita dai cosiddetti "automi non-deterministici". In tali meccanismi ogni simbolo letto non comporta necessariamente la transizione da uno stato a un altro unico stato, ma, più in generale, a una collezione di stati eventualmente vuota. A ogni istante della sua evoluzione si parla di una collezione di possibili stati e di un insieme di possibili configurazioni. La molteplicità degli stati che caratterizzano una situazione dell'automa non deve intendersi in senso probabilistico; piuttosto, potrebbe descriversi associando un indicatore luminoso a ogni stato e pensando che, a ogni istante dell'evoluzione, possono essere accesi più indicatori.

Un riconoscitore non-deterministico può possedere più stati iniziali e accetta tutte le stringhe che dagli stati iniziali conducono a una collezione di stati comprendente almeno uno stato finale. I riconoscitori non-deterministici costituiscono una classe più comprensiva dei deterministici, ma sono in grado d'individuare gli stessi linguaggi che si possono presentare con riconoscitori deterministici, anche se in quest'ultimo caso potrebbero essere necessari più stati interni.

Un'altra variante dei riconoscitori a stati finiti consente transizioni fra stati senza che la testina di lettura avanzi sul nastro di input. Anche questi riconoscitori, benché più generali dei precedenti, consentono di presentare solo linguaggi razionali.

Con i cosiddetti "automi a due direzioni" con una mossa si può avere uno spostamento della testina sul nastro sia verso destra che verso sinistra, come pure nessuno spostamento. Essi accettano le stringhe che inducono evoluzioni che si concludono in uno stato finale e con la testina di lettura a destra dell'ultimo simbolo. Anche con questi riconoscitori non si riscontra un ampliamento della gamma dei linguaggi accettabili.

Vari tipi di riconoscitori. - Un linguaggio può, dunque, essere riconosciuto da riconoscitori di tipi diversi; inoltre, non è difficile trovare riconoscitori dello stesso tipo a prima vista molto differenti, che accettano lo stesso linguaggio. Inoltre, abbiamo visto che un linguaggio può essere presentato con diverse modalità: un linguaggio razionale può essere presentato con un'espressione razionale (anzi, con diverse di tali espressioni) e con un riconoscitore a stati finiti. In linea generale, si può considerare che i linguaggi siano degli oggetti essenziali, mentre le loro presentazioni finite siano degli strumenti per la loro individuazione ampiamente intercambiabili. Siamo in presenza del cosiddetto "fenomeno della molteplicità" che si presenta sistematicamente nello studio di strutture informative e che costituisce un importante tema di studio. Tra le varie presentazioni di un linguaggio, o tra le diverse rappresentazioni di una struttura informativa, si pone il problema della scelta o della costruzione di quella più soddisfacente per semplicità (per es., riconoscitore del modello più semplice), per economia di costituenti (per es., riconoscitore con il minimo numero di stati), per chiarezza nell'indicare determinate proprietà dell'oggetto individuato. Solo nei casi più semplici s'impone un'unica presentazione "ottima". In genere, le esigenze sopra accennate sono contrastanti: una presentazione semplice può essere poco economica e lasciare in ombra determinate proprietà; il riconoscitore con minimo numero di stati di un linguaggio razionale in genere è non-deterministico; talune proprietà di un linguaggio possono essere chiarite solo con strumenti elaborati. Si pongono, quindi, i problemi di passare da una presentazione a un'altra, migliore secondo un certo metro, contenendo l'aumento di altri parametri di complessità.

Per estendere la capacità di presentazione dei riconoscitori è necessario che questi possano ricordare quanto letto sul nastro di input in modo da riuscire a distinguere fra un insieme di situazioni, quale che sia il loro numero, e da poter prendere successive decisioni sulla base di questi ricordi. I riconoscitori a stati finiti possono ricordare quanto letto solo attraverso gli stati: le situazioni che possono distinguere sono, quindi, in numero finito e quindi riescono a tener conto delle correlazioni che intercorrono tra elementi distanti nelle stringhe da analizzare solo in modo limitato. Un dispositivo di memoria superiore è il cosiddetto "deposito a pushdown", deposito che può contenere una pila di simboli che consente di leggere, inserire o eliminare solo nella parte superiore. In ogni istante in questo deposito può essere memorizzato solo un numero finito di simboli, ma non vi sono limitazioni su tale numero nel corso dell'evoluzione; il deposito a pushdown si dice, quindi, di capacità infinita. I riconoscitori a pushdown, come i riconoscitori di Rabin e Scott, possiedono un numero finito di stati interni e possono leggere da sinistra a destra un nastro di input; essi, però, a ogni istante decidono la mossa anche sulla base del simbolo letto in cima alla pila, e possono eliminare tale simbolo e sostituirlo.

I più semplici riconoscitori a pushdown possono inserire nel deposito un solo simbolo e quindi, in sostanza, sono in grado di ricordare solo un numero intero e di confrontare lunghezze di parti della stringa di input. Questi riconoscitori e i linguaggi associati si dicono "a contatore"; fra tali linguaggi si trova

Un riconoscitore a pushdown può operare in modo deterministico o non-deterministico: questi due tipi di riconoscitori sono in grado di presentare due classi diverse di linguaggi, dette rispettivamente dei "linguaggi context-free deterministici" e dei "linguaggi contextfree" tout court. Nella prima collezione si trovano il cosiddetto "linguaggio di Dyck", linguaggio costituito da sequenze di parentesi " (" e " ) ", che si accoppiano come nelle espressioni nelle quali delimitano sottoespressioni, e

nella seconda

Più flessibile del pushdown è il "deposito a stack", il quale può essere letto in ogni sua parte e, quindi, può fornire indicazioni più articolate di quelle espresse da un semplice simbolo. I riconoscitori a stack deterministici sono in grado di presentare una classe di linguaggi più ampia della collezione dei context-free; tra di essi si trovano

Una prestazione degli automi che consente di presentare una classe di linguaggi più ampia delle precedenti è la possibilità di modificare lo stesso nastro d'ingresso, cioè di controllarlo con una testina di lettura e scrittura. Si dice "riconoscitore linearmente limitato" (linear bounded automaton) un riconoscitore con un insieme finito di stati e con una testina di lettura e scrittura che può spostarsi in avanti e all'indietro sul nastro, ma limitatamente alle posizioni sulle quali è stata registrata la stringa da analizzare. I linguaggi accettabili dai riconoscitori linearmente limitati sono detti context-sensitive; tra di essi si trova

I riconoscitori linearmente limitati possono avere un comportamento deterministico e non-deterministico ma attualmente non è chiaro se i secondi abbiano portata superiore.

I riconoscitori aventi le capacità massime, in un senso che chiariremo più oltre, sono le "macchine di Turing". Di queste macchine formali sono stati studiati molti modelli che si sono trovati equivalenti. Il modello più semplice differisce dal riconoscitore linearmente limitato deterministico solo in quanto la testina di lettura e scrittura è in grado di muoversi anche sulle posizioni del nastro che inizialmente non erano occupate dalla stringa di input; il nastro è da pensarsi infinito e quindi non vi sono limiti alle possibilità di registrazione della macchina.

Questo, oltre alla capacità di trattare una collezione di linguaggi più ampia di quella dei context-sensitive, comporta anche che l'evoluzione di una tale macchina potrebbe non avere fine. In effetti, assegnata una stringa d'ingresso e avviata l'evoluzione, a un certo punto o l'evoluzione si è conclusa o non si è conclusa, ma è chiaro che proseguirà indefinitamente riciclando su un insieme finito di configurazioni oppure toccando configurazioni sempre diverse, oppure non è chiaro se proseguendo l'evoluzione la macchina potrà giungere a una delle precedenti situazioni (evoluzione indefinita). Ora, una stringa di input che porta a un'evoluzione finita è chiaro se appartiene o meno al linguaggio, mentre una stringa che porti a un'evoluzione senza arresto è da rifiutare; viceversa, nel caso di evoluzione indefinita non si può decidere se la stringa di input appartiene o meno al linguaggio. Quindi, la questione dell'appartenenza di una generica stringa a un linguaggio definito da una macchina di Turing non può sempre essere decisa. Un linguaggio per il quale tale questione può essere sempre decisa si dice "ricorsivo", mentre se esiste solo un meccanismo in grado di produrre sue stringhe in un ordine qualsiasi si dice "ricorsivamente enumerabile". Ora, con un tipico procedimento diagonale alla Cantor, si mostra che i linguaggi individuati da macchine di Turing sono ricorsivamente enumerabili: anzi, come vedremo, coincidono con essi. Dalla finitezza delle configurazioni assumibili da un automa linearmente limitato al quale sia assegnata una stringa di input, segue subito che i linguaggi context-sensitive sono ricorsivi, mentre con un procedimento diagonale s'individuano linguaggi ricorsivi e non context-sensitive.

Grammatiche a struttura di frase. - Un'altra modalità per la presentazione dei linguaggi si serve di meccanismi generativi, cioè di strumenti in grado di costruire le parole che stanno in un linguaggio; il complesso di tali meccanismi fornisce quindi linguaggi ricorsivamente enumerabili. A questi meccanismi si può dare la forma delle cosiddette "grammatiche a struttura di frase" introdotte da N. Chomsky. Formalmente una grammatica è individuata da una quaterna (T, X, P, S) ove T e X sono alfabeti disgiunti detti rispettivamente "alfabeto dei terminali" e "degli ausiliari", S è un particolare ausiliario detto "simbolo di partenza" e P un insieme finito di coppie di stringhe su T + X dette "produzioni" o "regole di riscrittura" e indicate con scritture del tipo x → y. Il meccanismo generativo di una grammatica G si basa su catene di derivazione della forma S ⇒ w₁ ⇒ w₂ ⇒ ... ⇒ w_s, ove w ⇒ w′ se in w si trova una sottostringa che sia primo membro di una produzione x → x′ e se w′ si ottiene rimpiazzando, in w, x con x′. Le precedenti w_i si dicono "forme sentenziali" di G; una derivazione come la precedente nella quale w_s è costituita soltanto da lettere terminali si dice che "genera w_s"; l'insieme delle stringhe generate nel modo suddetto è chiamato "linguaggio generato da G" ed è indicato con L(G). Anche le grammatiche presentano una grande varietà di tipi distinti dai tipi di produzioni che le compongono; come per i riconoscitori s'individua una gerarchia di grammatiche via via più complesse in grado di generare classi di linguaggi via via più ampi.

Una grammatica si dice "lineare a destra" quando le sue produzioni hanno la forma A → aB o A → a ove A e B sono ausiliari e a terminale; non è difficile mostrare che i linguaggi generati da tali grammatiche coincidono con i razionali. Una grammatica si dice context-free se le sue produzioni hanno la forma A → w, ove A è un ausiliario e w una stringa generica e si dimostra che tali grammatiche generano i linguaggi context-free, cioè i linguaggi accettati dai riconoscitori a pushdown non-deterministici. Una grammatica si dice context-sensitive se le sue produzioni hanno la forma x₁ → x₂ con x₁ = yAz e x₂ = ywz con A ausiliario ed y, w e z stringhe generiche, w ≠ e. I linguaggi generati da queste grammatiche si trovano coincidere con i context-sensitive. Si dimostra, infine, che i linguaggi generati da una grammatica senza restrizioni sulle produzioni coincidono con quelli riconosciuti da macchine di Turing: essi sono detti "ricorsivamente enumerabili".

Abbiamo quindi individuato linguaggi costituenti classi sempre più estese, i linguaggi razionali, i context-free, i context-sensitive e i linguaggi ricorsivamente enumerabili, i quali possono essere studiati sia con riconoscitori che con grammatiche. Questi linguaggi, notevoli proprio per questa proprietà, si dicono costituire la "gerarchia di Chomsky" e vengono anche detti rispettivamente linguaggi di tipo 3, 2, 1 e 0.

Macchine di Turing. - L'equivalenza fra macchine di Turing e grammatiche di tipo 0 si collega a studi di fondamenti della matematica sviluppati nei primi 40 anni del secolo riguardanti i sistemi assiomatici finitistici e la definizione di algoritmo effettivo e di calcolabilità. Un sistema assiomatico finitistico è costituito da un insieme finito di stringhe dette "assiomi" e da un insieme finito di regole d'inferenza che consentono di derivare dagli assiomi le stringhe costituenti i teoremi del sistema stesso; la loro importanza è dovuta alla tendenza risalente alla scuola formalistica di D. Hilbert di costruire su di essi ogni teoria matematica. Ora, a un tale sistema si può dare una forma detta "canonica" nella quale le regole d'inferenza assumono l'aspetto di produzioni. Si hanno vari tipi di sistemi assiomatici fissando i tipi ammissibili per le produzioni: se le produzioni hanno la forma xyz → xy′z si ha un "sistema semithueiano", se accanto a ciascuna delle precedenti produzioni si ha pure la xy′z → xyz si parla di "sistema di Thue", se le produzioni hanno la forma xy → yx′ il sistema si dice "normale" e se accanto a ciascuna delle precedenti produzioni si ha pure la yx′ → xy si ha un sistema "in forma di Post". Classici risultati dimostrano l'equivalenza di questi sistemi, cioè l'uguaglianza della loro portata; collegando assiomi e simbolo di partenza è poi facile mostrare l'equivalenza dei sistemi assiomatici finitistici con le grammatiche di tipo 0 e quindi con le macchine di Turing.

Una macchina di Turing, oltre che al riconoscimento di un linguaggio, può essere finalizzata alla generica trasformazione di una data stringa nella stringa ottenibile al suo arresto; inoltre, quando un particolare simbolo assume il ruolo di delimitatore, essa è in grado di trasformare più stringhe in altre stringhe. A questo punto, la macchina di Turing può tranquillamente pensarsi come un meccanismo in grado di svolgere elaborazioni del tutto generali purché riguardanti entità, numeriche o d'altro genere, codificabili completamente e senza ambiguità con stringhe finite. Similmente si può attribuire una portata assai generale al problema dell'appartenenza di una stringa a un linguaggio: in effetti, nel caso di un linguaggio costituito da tutti i teoremi di una data teoria o dalle formule di un certo calcolo, la possibilità di decidere l'appartenenza equivale alla conoscenza completa della teoria e al dominio completo del calcolo. La speranza che questo possa effettuarsi in ogni caso in modo automatico è però vanificata dall'esistenza di linguaggi ricorsivamente enumerabili non ricorsivi.

Della macchina di Turing si possono dare un gran numero di varianti che risultano equivalenti al modello originale precedentemente introdotto. Innanzitutto si trovano forme canoniche particolarmente economiche: una macchina di Turing, infatti, può essere simulata da una macchina con due soli stati oppure con una macchina che operi su due soli simboli. D'altra parte vi sono macchine di Turing di aspetto più articolato, dotate di più nastri ciascuno dei quali può essere letto e/o scritto, o dotate di dispositivi di memoria a più dimensioni finiti o infiniti e controllabili anche con diverse testine di lettura e scrittura. Un'altra macchina formale equivalente è la cosiddetta "macchina di Wang", la quale è costituita come una macchina di Turing, ma che si evolve secondo una sequenza di istruzioni tra le quali si può saltare, sequenza molto simile a un programma per l'elaboratore elettronico. Le equivalenze accennate suggeriscono che una macchina di Turing è in grado di svolgere tutti i compiti che può compiere uno degli odierni elaboratori elettronici o un qualunque operatore automatico, umano o materiale. Esse poi presentano il vantaggio, evidentemente solo teorico, di disporre di supporti d'informazione di capacità illimitata.

Le stringhe elaborate da una macchina di Turing, in particolare, si può pensare rappresentino numeri interi e a essa quindi si può associare una funzione di variabili intere a valori interi che viene detta "T-computabile". Le precedenti considerazioni giustificano ampiamente la congettura di Turing secondo la quale la totalità delle funzioni effettivamente calcolabili coincidono con le T-computabili. Equivalentemente si ha che le macchine di Turing costituiscono dei modelli per la totalità degli algoritmi effettivi mentre i sistemi assiomatici finitistici e le grammatiche di tipo 0 costituiscono strumenti generali per la dimostrabilità effettiva. Un'ulteriore giustificazione della congettura di Turing viene dalla dimostrazione che le funzioni T-computabili coincidono con altre due classi di funzioni proposte come totalità delle funzioni calcolabili, cioè con le funzioni definibili con il cosiddetto "λ-calcolo" di A. Church e con le funzioni generali ricorsive di K. Gödel. In ogni caso le macchine di Turing e tutte le altre strutture computazionali equivalenti sono modelli sufficienti per le elaborazioni che si possono effettuare con le odierne apparecchiature per l'elaborazione dei dati.

Lo studio delle precedenti strutture chiarisce anche i limiti degli algoritmi effettivi. Innanzi tutto, dall'osservazione che ogni macchina di Turing e ogni grammatica di tipo 0 su un alfabeto A possono esprimersi con una stringa finita, segue che tali meccanismi formali sono numerabili; il teorema di Cantor applicato ad A dice, invece, che i linguaggi su A hanno la cardinalità del continuo e quindi esistono linguaggi che non sono individuabili con alcun procedimento effettivo. Inoltre, l'esistenza di una macchina di Turing detta "universale" in grado di simulare il comportamento di ogni altra macchina consente di mostrare che il problema dell'arresto di una macchina di Turing non è decidibile con alcun procedimento effettivo. In conseguenza di questo è chiarita l'esistenza di problemi per i quali non si può trovare alcun algoritmo effettivo in grado di risolverli o equivalentemente di questioni per le quali non esiste un procedimento generale in grado di decidere per il sì o per il no; e ancora è provata l'esistenza di linguaggi ricorsivamente enumerabili non ricorsivi. Quest'ultima asserzione costituisce una forma astratta del teorema di Gödel che stabilisce che ogni sistema assiomatico consistente e adeguato a esprimere un insieme di asserzioni sufficientemente ampio sui numeri interi è incompleto, cioè possiede teoremi veri che non possono essere provati.

Per i vari problemi che s'incontrano studiando i linguaggi o altri sistemi discreti riguardanti l'elaborazione dei dati è importante stabilire se possono essere risolti o decisi con procedimenti effettivi generali o se non esiste alcuno di tali algoritmi. In questa seconda alternativa sarà necessario studiare procedimenti ad hoc che riguardano situazioni il più possibile ampie ma comunque non generali. L'insolubilità e l'indecidibilità di varie questioni è dimostrata attraverso il problema di corrispondenza o della doppia sciarada di E. L. Post, conseguenza diretta dell'indecidibilità del problema dell'arresto della macchina di Turing. Questo problema indecidibile si enuncia dicendo che non esiste alcun procedimento effettivo il quale, date due sequenze di stringhe x₁, ..., x_n e y₁, ..., y_n, decida se esista una sequenza di interi i₁, ... i_m, compresi tra 1 e n, tali che x_i1 x_i2 ... x_im = y_i1 y_i2 ... y_im.

A livello dei linguaggi razionali e degli automi a stati finiti sono risolubili sostanzialmente tutti i problemi di portata generale; in particolare, sono effettivamente determinabili le espressioni razionali e i riconoscitori che forniscono i linguaggi ottenuti come risultati di un gran numero di operazioni su altri linguaggi razionali. Per questi fatti e per la semplicità del modo di operare dei riconoscitori a stati finiti e di automi dello stesso livello come i trasduttori di Mealy e di Moore (macchine in grado, oltre che di analizzare una stringa, di trasformarla in una seconda), vari problemi di elaborazione di dati e vari modelli vengono ricondotti a tali meccanismi e ai linguaggi razionali. Purtroppo, queste strutture spesso richiedono schematizzazioni troppo semplici: per es., consentono di trattare solo dei frammenti di linguaggi di programmazione che non comprendono le espressioni algebriche riconducibili ai linguaggi di Dyck. Gli automi a stati finiti consentono, invece, una trattazione sintetica e completa dei cosiddetti circuiti combinatori, circuiti elettronici con componenti del tipo AND, OR e NOT.

Lo studio dei linguaggi razionali e degli automi a stati finiti si sviluppa nella direzione di una classificazione dettagliata e sistematica: dato che questi oggetti sono associati a semigruppi finiti, questi studi si confondono con la teoria di tali strutture algebriche, anche se queste ultime rispecchiano solo alcuni aspetti essenziali degli automi e dei linguaggi. Notevole, a questo proposito, è lo sviluppo della teoria di K. Krohn e J. L. Rhodes tendente a individuare degli elementi costitutivi essenziali degli automi che, in termini algebrici, corrispondono a sottogruppi semplici e a sottosemigruppi che non siano gruppi. Questa teoria ha sviluppato classificazioni secondo complessità degli automi da riferirsi sostanzialmente alla lunghezza di catene che generalizzano ai semigruppi finiti le catene di Jordan-Hölder per i gruppi: contemporaneamente vengono cercate applicazioni di questi risultati a svariati settori che vanno dalla fisica alla psicologia.

Linguaggi context-free. - Lo studio dei linguaggi context-free, delle grammatiche e degli automi associati, è sensibilmente più complesso. Data una tale grammatica, G è decidibile se L(G) è vuoto, finito o infinito e se un suo simbolo può essere eliminato senza ridurre tale linguaggio. Viceversa, non è decidibile se L(G) sia razionale, se G sia ambigua, cioè fornisca derivazioni strutturalmente diverse per qualche sua stringa, se L(G) possa essere generato da una grammatica non ambigua e se il suo complementare sia context-free, razionale o finito. Inoltre, date due grammatiche context-free G₁ e G₂, non è decidibile se sia L(G₁) = L(G₂) o se L(G₁) ⊆ L(G₂), se L(G₁) ⋂ L(G₂) sia vuoto, o finito, o razionale, o context-free. A tali questioni generali possono ridursi problemi pratici riguardanti linguaggi programmativi che sostanzialmente possono trattarsi in un ambito context-free: si pone, quindi, il problema d'individuare sottoclassi più ristrette di questi linguaggi per le quali i problemi sopra accennati sono dominabili con procedimenti effettivi; questo si verifica spesso per i linguaggi context-free deterministici. Alcuni studi generali sulla decidibilità mirano a collegare diversi problemi di decidibilità indipendentemente dalle collezioni di linguaggi considerate.

Lo studio dei linguaggi context-free è stato sviluppato soprattutto con lo scopo di precisare modelli per la descrizione sintattica dei linguaggi di programmazione e per la loro analisi sintattica nell'ambito del processo di compilazione, cioè nel processo di traduzione dei programmi in istruzioni comprensibili, più o meno direttamente, da parte dell'elaboratore elettronico. Così una grammatica context-free ha consentito di specificare quasi interamente le sintassi di un linguaggio di programmazione come l'ALGOL 60 e i meccanismi per la traduzione di linguaggi programmativi che siano diretti dalla sintassi, cioè che siano applicabili a intere classi di linguaggi, si basano su automi a pushdown. Accade, però che i linguaggi context-free sono inadeguati a rappresentare tutte le caratteristiche dei linguaggi di programmazione; per es., non si ha modo di dominare la occorrenza multipla di un certo termine, in accordo con il fatto che

non è context-free; similmente l'interpretazione di certi brani di programma richiede di far riferimento a dichiarazioni preliminari, e anche questo non è dominabile con una grammatica context-free. Queste esigenze potrebbero essere soddisfatte nell'ambito di una grammatica context-sensitive, ma muovendosi in tale ambito si dovrebbero utilizzare algoritmi estremamente inefficienti. D'altra parte, le grammatiche sia context-free che context-sensitive non risultano adeguate a specificare la semantica dei linguaggi programmativi, cioè il significato dei programmi in termini delle operazioni che essi richiedono al calcolatore. Per questo sono state sviluppate estensioni delle grammatiche contextfree con meccanismi specifici riguardanti la rappresentazione e il significato degli elementi del programma, la loro sistemazione in memoria e la rappresentazione della sequenza delle operazioni richieste. D'altra parte per ragioni di efficienza sono state studiate classi di grammatiche context-free che consentono un'analisi sintattica molto rapida di frammenti di programmi: per questi motivi, sono state introdotte, per es., le grammatiche denominate LR(k), LL(k), a precedenza e a operatori con precedenza studiate insieme con i relativi algoritmi per l'analisi sintattica (passing).

Altri indirizzi di ricerca. - Recentemente è stata sviluppata la cosiddetta "semantica formale", disciplina che si propone di studiare modelli matematici tendenzialmente generali sul significato dei linguaggi in termini di operazioni di elaborazione di dati. In collegamento con questi studi è stata, inoltre, sviluppata una teoria degli schemi di programma, cioè di schemi rappresentanti intere classi di programmi, con gli scopi di provare su una base generale proprietà di un programma quali la sua correttezza, il fatto che una sua esecuzione giunga a termine, la sua equivalenza con altri programmi che possano risultare vantaggiosi. Sempre in relazione alle esigenze dei linguaggi programmativi, occorre ricordare l'utilizzo delle cosiddette "grammatiche a due livelli o di A. van Wijngaarden" che consentono di definire linguaggi di programmazione di grande generalità quali l'ALGOL 68, linguaggi che consentono una definizione preliminare molto libera delle caratteristiche specifiche degli oggetti delle elaborazioni richieste, definizioni preliminari che possono pensarsi in termini di generazione preliminare con una grammatica di una seconda grammatica che specificherà un linguaggio da utilizzarsi per esigenze particolari.

Un'altra profonda motivazione allo studio dei linguaggi formali e delle grammatiche è la ricerca di modelli matematici per la descrizione e possibilmente per il trattamento automatico delle lingue naturali. Questi problemi si sono rivelati sensibilmente più complessi di quelli posti dai linguaggi artificiali: i linguaggi context-free sono in grado di fornire modelli solo per frammenti molto ridotti di lingue naturali e anche in questo caso si presenta la necessità di riferirsi a grammatiche context-sensitive e di affrontare problemi semantici. Complessivamente per le lingue naturali sono stati proposti vari modelli formali dei quali, però, nessuno si è imposto ampiamente; in questo settore si hanno poi dei risultati limitativi: per es., l'indecidibilità dell'ambiguità delle grammatiche context-free limita la probabilità di metodi efficienti per la traduzione automatica.

Le insufficienze delle grammatiche context-free e le difficoltà presentate dalle grammatiche context-sensitive hanno fatto sviluppare lo studio di numerose classi di linguaggi intermedie ottenute sia arricchendo i meccanismi context-free con varianti, sia restringendo i meccanismi contextsensitive. D'altra parte, per studiare la complessità degli algoritmi in termini generali, cioè indipendenti dall'elaboratore usato, si sono sviluppati studi sui linguaggi o sulle computazioni effettuabili da macchine di Turing con restrizioni sull'uso di memorie e sui tempi dell'evoluzione espressi in termini di lunghezza della stringa di input, e anche in tal modo si sono individuate svariate collezioni di linguaggi. Questa proliferazione delle classi di linguaggi hanno condotto all'esigenza di un loro inquadramento generale. A questo proposito sono stati proposti schemi per intere collezioni di linguaggi come gli automi a pallone e le famiglie astratte di linguaggi e di automi, definite queste ultime a partire da proprietà di chiusura di tipo algebrico.

Per concludere, ricordiamo che negli ultimi anni sono state sviluppate ampiamente e in varie direzioni ricerche su linguaggi costituiti da oggetti di natura più complessa delle stringhe, con l'obiettivo di mettere a punto procedimenti efficienti per l'elaborazione di strutture informative complesse. A questo proposito, limitiamoci semplicemente a citare gli automi cellulari agenti su tassellazioni risalenti a J. Von Neumann, i linguaggi a intorni di B. V. Borshov e M. V . Homiakov, i linguaggi di grafi e gli automi ad albero di J. W. Thatcher, i sistemi e i linguaggi sviluppamentali di A. Lindenmayer.

Bibl.: A. M. Turing, On computable numbers with an application to the Entscheidungs-problem, in Proc. London Math. Soc., 2, XLII (1936), p. 230 segg.; E. L. Post, Formal reduction of the general combinatorial decision problem, in Am. J. Math., LXV (1943), p. 197 segg.; W. McCulloch, W. Pitts, A logical calculus of the ideas immanent in nervous activity, in Bull. Math. Biophys., V (1943), p. 115 segg.; S. C. Kleene, Representation of events in nerve nets and finite automata, in Automata studies (a cura di C. E. Shannon, M. McCarthy), Annals of Math. Studies, 1956, p. 3 segg.; M. Davis, Computability and unsolvability, New York 1958; N. Chomsky, On certain formal properties of grammars in Information and control, II (1959), p. 137 segg.; M. O. Rabin, D. Scott, Finite automata and their decision problem, in IBM J. Res. Dev., III (1959), p. 114 segg.; Y. I. Ianov, The logical schemas of algorithms, in Problems of Cybernetics, vol. I, Oxford 1960; N. Chomsky, M. P. Schützenberger, The algebraic theory of context-free languages, in Compute programming and formal systems (a cura di P. Brafford e D. Hirschberg), Amsterdam 1963, p. 118 segg.; R.W. Floyd, Syntactic analysis and operator precedence, in J. ACM, X (1063), p. 316 segg.; Y. Bar-Hillel, Language and information, Reading, Mass. 1964; A. Cobham, The intrinsic computational difficulty of functions, in Proc. 1964 Congress for logic, mathematics and philosophy of science, Amsterdam 1964, p. 24 segg.; J. Hartmanis, R. E. Stearns, On the computational complexity of algorithms, in Trans. Amer. Math. Soc., CXVII (1975), p. 285 segg.; D. E. Knuth, On the translation of languages from left to right, in Information and control, VIII (1065), p. 607 segg.; S. Ginsburg, The mathematical theory of context-free language, New York 1966; J. Von Neumann, Theory of self reproducing automata (curato e completato da A. W. Burks), Università dell'Illinois 1966; M. Blum, A machine independent theory of the complexity of recursive functions, in J. ACM, XIV (1967), p. 322 segg.; S. Kuno, Computer analysis of natural languages, in Mathematical aspects of computer science (a cura di J.T. Schwartz), Providence (RI) 1967; M. Minsky, Computation: finite and infinite machines, Londra 1967; H. Jr. Rogers, Theory of recursive functions and effective computability, New York 1967; A. V. Aho, J. D. Ullman, The theory of languages, in Math. Systems Theory, II (168), p. 97 segg.; Autori vari, Algebraic theory of machines, langauges and semigroups (a cura di M. A. Arbib), New York e Londra 1968; M. A. Arbib, Theories of abstract automata, Londra 1969; J. E. Hopcroft, J. D. Ullman, Formal languages and their relations to automata, Reading, Mass., 1969; R. E. Kalman, P. L. Falb, M. A. Arbib, Topics in mathematical systems theory, New York 1969; A. V. Gladkij, Leçons de linguistique mathématique, Parigi 1970; M. Gross, A. Lentin, Notions sur les grammaires formelles, ivi 1970; Z. Manna, Second order mathematical theory of computation, in Proc. II annual ACM Symposium on theory of compunting, 1970, p. 158 segg.; Autori vari, Complexity of computer computations (a cura di R. E. Miller, J. W. Thatcher), New York 1970; J. W. Thatcher, Generalized sequential machines, in J. Computer and System Sciences, IV (1970), p. 339 segg.; J. H. Conway, Regular algebra and finite machines, Londra 1971; Autori vari, Symposium on semantics of algorithmic languages (a cura di E. Engeler), Berlino 1971; A. P. Ershov, Theory of program schemata, in Proc. IFIP Congress 1971, Amsterdam 1971, p. 144 segg.; D. Gries, Compiler construction for digital computers, New York 1971; A. Paz, Introduction to probabilistic automata, ivi 1971; D. Scott, Lattice theory, data types and semantics, in Proc. New York University symposium on areas of current interest in computer science, Londra 1971; A. Lentin, Equations dans les monoïdes libres, Parigi 1972; A. V. Aho, J. D. Ullman, The theory of parsing, translation and compiling, vol. I, Londra 1972; vol. 2, ivi 1973; Autori vari, Currents in the theory of computing (a cura di A.V. Aho), ivi 1973; B. V. Borshov, M. V. Homiakov, Aksiomaticheskij padhod k opisaniu formal' nuyh iasuikov, in Matematicheskaja lingvistika, Nauchnoi i technicheskoi informacij, Akademij Nauk SSSR, 1973; A. K. Chandra, On the properties and applications of program schemas, Ph. D. thesis, Stanford University 1973; A. Salomaa, Formal languages, New York 1973; S. Eilemberg, Automata, languages and machines, vol A. ivi 1974; vol. B, ivi 1976; B. Tilson, On the complexity of finite semigroups, in J. Pure Appl. Algebra, V (1074), p. 187 segg.; S. Ginsburg, Algebraic and automata-theoretic properties of formal languages, Amsterdam 1975; Autori vari, Mathematical foundations of computer science (a cura di G. Goose, J. Hartmanis), Berlino 1975; G. T. Herman, G. Rozenberg, A. Lindenmayer, Developmental systems and languages, Amsterdam 1975; A. Van Wijngaarden e altri, Revised report on the algorithmic language ALGOL 68, in Acta informatica, V. (1975), p. 1 segg.; R. Milne, C. Strachey, A theory of programming language semantics, parte a, Londra 1976; parte b, ivi 1976; Autori vari, Automata, languages, development (a cura di A. Lindenmayer, G. Rozenberg), Amsterdam 1976; Autori vari, Theoretical computer science, 3rd GI Conference, Berlino 1977.