Fondamenti dell'Informatica: Linguaggi Formali e Automi

Vincenzo Manca

I corsi dei primi tre anni, specialmente quelli di tipo matematico, algoritmico e programmativo.

La studio delle principali classi di linguaggi formali ed automi, con particolare riguardo ai paradigmi emergenti di modelli di calcolo.

Il corso intende: i) Analizzare le più importanti classi di linguaggi formali e dei relativi sistemi di riscrittura (RE, CS, CF, LIN, REG, OL, MAT, HL, ...) con le loro varianti più importanti ed i principali risultati di equivalenza, normalizzazione, chiusura e decidibilità; ii) Presentare un quadro unificante dei vari formalismi di manipolazione simbolica e di alcuni recenti modelli di calcolo che sono alla frontiera della ricerca attuale (DNA e Molecular Computing).

This course intends: i)to analyze the main classes of formal languages (RE, CS, CF, LIN, REG, OL, MAT, HL, ...) with their important variants and relevant results of normalization, closure and decidability; ii) to present a unifying framework for formalisms of symbolic manipulation and for some recent computation models that are emerging in the actual research (DNA e Molecular Computing).

Operazioni su stringhe e linguaggi, Meccanismi combinatori, Sistemi di Post, Grammatiche e Automi.
Analisi della Gerarchia di Chomsky: Linguaggi fondamentali, Teoremi di universalità, equivalenza ed inclusione. Teorema di Kleene sulla regolarità, Teorema di Nerode sulla minimalità, Teoremi fondamentali di chiusura e normalizzazione (Bar-Hillel, Kuroda, Savitch, Shannon).
Meccanismi di regolazione: classi di linguaggi tramite regolazione.
Automi e trasduttori.
Sistemi di Lindenmayer, di Marcus, Head, Paun. Parametri di classificazione dei sistemi di derivazione di stringhe. Le forme di descrizione dell'accrescimento tripartito.
Modelli di stringhe e Teorie monoidali: universalità e rappresentabilità.
Sistemi monoidali nella rappresentazione di sistemi complessi.
Basi e motivazioni biochimiche del calcolo basato sullo 'splicing'.
Lemmi di regolarità e universalità dello 'splicing'.
Cenni sugli sviluppi e sulle applicazioni dei sistemi molecolari per la manipolazione simbolica.

1. DNA Computing: New Computing Paradigms, G. Paun, G. Rozerberg, A. Salomaa, Springer-Verlag, Berlin, 1998.
2. Rozenberg G., Salomaa A. (eds.), Handbook of Language theory, 3 Voll., Springer-Verlag, Berlin, 1997.

Scritto e orale