Linguaggi formali e automi
Corso da me tenuto alla FILS nel periodo 2010–2012, in un contesto piuttosto inatteso: la disciplina era stata inizialmente assegnata a un ex studente della Facoltà di Automatica, che non prese poi servizio. La assunsi io, potendo così tornare a un territorio che conoscevo molto bene fin dagli anni Settanta, quando avevo insegnato Teoria degli automi e Teoria dei linguaggi formali.
Non dispongo più delle note del corso, ma la scheda della disciplina e la bibliografia recuperata sono sufficienti per ricostruirne il profilo e la struttura generale.
Riferimenti essenziali
- Istituzione: Università POLITEHNICA di Bucarest
- Facoltà: FILS – Facoltà di Ingegneria in Lingue Straniere
- Semestre: 5
- Periodo di insegnamento: 2010–2012
- Titolo in romeno: Limbaje formale și automate
- Titolo in inglese: Formal Languages and Automata
- Struttura: 28 ore di lezione + 14 ore di esercitazioni
- Crediti: 3
- Prerequisiti: Matematica discreta, Strutture dati e algoritmi
Il posto del corso nella mia attività didattica
Per me questo corso rappresentò un ritorno a una delle radici della mia formazione universitaria e professionale. Nei primi anni della mia carriera, la teoria degli automi e la teoria dei linguaggi formali furono discipline centrali, sia nell’insegnamento, sia nel modo in cui compresi in seguito i linguaggi di programmazione, i compilatori e i modelli formali del software.
Insegnarlo alla FILS, in una fase tarda della mia carriera, non fu quindi un’improvvisazione, ma la ripresa, in una chiave diversa e per un’altra generazione di studenti, di una direzione antica e molto importante della mia attività didattica.
Obiettivo del corso
La scheda della disciplina afferma chiaramente che questo corso forniva le basi necessarie per un approccio più avanzato ai linguaggi di programmazione, agli algoritmi e alle strutture dati, alla progettazione di applicazioni, all’analisi dei problemi, alla validazione dei dati, all’interpretazione e alla rappresentazione simbolica, nonché ad applicazioni quali l’elaborazione del linguaggio naturale. Al termine del corso, lo studente doveva essere in grado di comprendere i concetti e i metodi essenziali della teoria dei linguaggi formali e della teoria degli automi e di utilizzarli in applicazioni diverse.
Struttura del corso
1. Linguaggi e loro specificazione finita
Il corso iniziava con la nozione di linguaggio e con il problema della specificazione finita di un linguaggio, cioè proprio con la domanda che sta alla base dell’intera disciplina: come descrivere rigorosamente insiemi infiniti di stringhe mediante meccanismi finiti.
2. Grammatiche e gerarchia di Chomsky
Seguivano l’introduzione delle grammatiche formali, la relazione tra grammatiche e linguaggi e la gerarchia di Chomsky. Qui lo studente entrava in contatto con le differenze tra le classi di linguaggi e con il posto di ciascuna classe nel quadro della teoria della computazione.
3. Alberi di derivazione per grammatiche indipendenti dal contesto
Una sezione distinta era dedicata agli alberi di derivazione, cioè alla forma strutturale delle derivazioni nelle grammatiche indipendenti dal contesto. Questa costituisce uno dei ponti importanti tra la teoria dei linguaggi e le successive tecniche di compilazione.
4. Automi finiti
Il corso passava poi agli automi finiti, confrontando DFA e NFA, i linguaggi da essi riconosciuti e i classici problemi di minimizzazione. Nello stesso contesto compariva il legame tra automi, espressioni regolari e grammatiche regolari.
5. Insiemi regolari ed espressioni regolari
I linguaggi regolari venivano presentati mediante più forme equivalenti: automi finiti, espressioni regolari e grammatiche regolari. Questa equivalenza costituisce uno dei nuclei più eleganti e formativi dell’intero corso.
6. Forme normali
Un’altra sezione importante riguardava le forme normali di Chomsky e Greibach, cioè le trasformazioni standard delle grammatiche indipendenti dal contesto. Esse preparano sia lo studio dei parser sia la comprensione della struttura interna delle grammatiche.
7. Automi a pila
Il corso comprendeva gli automi a pila, i loro criteri equivalenti di accettazione e la relazione con le grammatiche indipendenti dal contesto. Qui lo studente osservava il passaggio dalla memoria finita degli automi finiti a una forma più potente di calcolo simbolico.
8. Macchina di Turing e computabilità
Nella parte finale, il corso arrivava alla macchina di Turing e alla nozione di computabilità. La disciplina si concludeva così aprendosi al tema generale dei limiti del calcolo, proprio là dove l’informatica teorica si collega ai fondamenti dell’intero settore.
Applicazioni
I laboratori seguivano da vicino la struttura del corso: grammatiche di Chomsky e alberi di derivazione, trasformazioni delle grammatiche indipendenti dal contesto, DFA e relativi linguaggi, NFA e transizioni λ, equivalenza NFA–DFA, espressioni regolari, grammatiche regolari, pumping lemma, automi a pila e loro equivalenza con le grammatiche indipendenti dal contesto, quindi macchina di Turing standard e computabilità.
Dalla scheda risulta chiaramente che le esercitazioni miravano sia alla manipolazione pratica degli automi finiti e degli automi con memoria infinita, sia all’esperienza diretta nella specificazione dei linguaggi e nei problemi di computabilità.
Valutazione
La valutazione era composta per il 20% dall’attività di laboratorio, per il 20% dai compiti a casa e per il 60% dall’esame finale. Quest’ultimo aveva una struttura interessante ed equilibrata: un breve test, una domanda teorica più ampia e una parte dedicata ai problemi. Per superare il corso era necessario raggiungere una soglia minima sia nell’attività applicativa, sia nella verifica finale.
Bibliografia
La bibliografia recuperata è per me molto significativa, perché accosta i miei manuali precedenti ad alcuni classici titoli internazionali.
- L. D. Șerbănați, Limbaje și compilatoare. Partea I: Limbaje de programare, Tip. IPB, 1981.
- L. D. Șerbănați, Limbaje și compilatoare. Partea II: Programare în Pascal, Tip. IPB, 1982.
- L. D. Șerbănați, Limbaje și compilatoare. Partea III: Introducere în sisteme formale; Partea IV: Proiectarea compilatoarelor, Tip. IPB, 1983.
- L. D. Șerbănați, Limbaje de programare și compilatoare, Editura Academiei RSR, 1987.
- M. Sipser, Introduction to the Theory of Computation, 1997.
- M. Moret, The Theory of Computation, 1998.
- T. A. Sudkamp, Languages and Machines. An Introduction to the Theory of Computer Science, 1998.
Nell’appendice bibliografica compaiono anche classici testi sui compilatori, come Aho–Sethi–Ullman, rafforzando così la naturale relazione tra questa disciplina e i corsi sui linguaggi e sui compilatori.
Significato del corso
Nell’insieme della mia attività didattica, questo corso ha un significato particolare. Mostra che, dopo decenni di insegnamento e ricerca in altri ambiti dell’informatica, potevo tornare senza difficoltà a uno dei suoi nuclei teorici più antichi. E forse proprio questo ritorno tardivo gli conferisce un certo fascino.
Per gli studenti, il corso offriva fondamenti. Per me aveva anche un significato biografico: riprendeva un filone didattico iniziato molto tempo prima, negli anni in cui la teoria degli automi e la teoria dei linguaggi formali facevano parte delle discipline attraverso le quali si costruiva il rigore dell’informatica universitaria.