Automi E Linguaggi 2025/2026

TEORIA DEI LINGUAGGI

Linguaggi regolari e automi finiti deterministici e non deterministici. Espressioni regolari e loro equivalenza con gli automi finiti. Pumping lemma per i linguaggi regolari. Chiusura dei linguaggi regolari rispetto a vari operatori. Linguaggi "context-free" e loro grammatiche. Automi pushdown non deterministici e loro equivalenza con le grammatiche "context-free". Pumping lemma per i linguaggi "context-free". Automi pushdown deterministici, linguaggi "context-free" deterministici e loro proprietà. Grammatiche LR(k), LR(1), LR(0). Il parser di Earley per grammatiche "context-free".

TEORIA DELLA CALCOLABILITÀ

Macchine di Turing. Linguaggi ricorsivamente enumerabili linguaggi ricorsivi. Varianti di macchine di Turing e loro equivalenza. Macchine di Turing non deterministiche. Enumeratori. Definizione di algoritmo e tesi di Church-Turing. Problemi decidibili e indecidibili. Il metodo di diagonalizzazione. Esempi di linguaggi non decidibili. Macchina di Turing universale. Riduzione tra linguaggi. Il problema PCP (Post Correspondence Problem). Riducibilità many-one. Funzioni calcolabili. Teorema di Rice. Teorema della ricorsione. Sistemi formali, modelli e teorie dei modelli. Decidibilità di teorie logiche. Riducibilità di Turing e macchine di Turing ad oracolo. Complessità di Kolmogorov.

TEORIA DELLA COMPLESSITÀ

Complessità temporale. La classe P. La classe NP. Esempi di problemi in P ed in NP. La classe co-NP. La classe EXPTIME. NP-hardness e NP-completezza. Il problema di soddisfacibilità SAT. Teorema di Cook-Levin. Esempi di problemi NP-completi: SAT, 3SAT, CLIQUE, VERTEX COVER, HAMPATH, UHAMPATH, SUBSET SUM. Complessità spaziale. Il teorema di Savitch. Spazio logaritmico: classi L, NL, coNL

---

Fonte: GOMP