1 Automi: metodo e follia
1.1 Perche' studiare la teoria degli automi
1.2 Introduzione alle dimostrazioni formali
1.3 Altre forme di dimostrazione
1.4 Dimostrazioni induttive
1.5 I concetti centrali della teoria degli automi
1.6 Riepilogo
1.7 Bibliografia

2 Automi a stati finiti
2.1 Una descrizione informale degli automi a stati finiti
2.2 Automi a stati finiti deterministici
2.3 Automi a stati finiti non deterministici
2.4 Un'applicazione: ricerche testuali
2.5 Automi a stati finiti con epsilon-transizioni
2.6 Riepilogo
2.7 Bibliografia

3 Espressioni e linguaggi regolari
3.1 Espressioni regolari
3.2 Automi a stati finiti ed espressioni regolari
3.3 Applicazioni delle espressioni regolari
3.4 Proprieta' algebriche per le espressioni regolari
3.5 Riepilogo
3.6 Bibliografia

4 Proprieta' dei linguaggi regolari
4.1 Dimostrare che un linguaggio non e' regolare
4.2 Proprieta' di chiusura dei linguaggi regolari
4.3 Problemi di decisione per i linguaggi regolari
4.4 Equivalenza e minimizzazione di automi
4.5 Riepilogo
4.6 Bibliografia

5 Grammatiche e linguaggi liberi dal contesto
5.1 Grammatiche libere dal contesto
5.2 Alberi sintattici
5.3 Applicazioni delle grammatiche libere dal contesto
5.4 Ambiguita' nelle grammatiche e nei linguaggi
5.5 Riepilogo
5.6 Bibliografia

6 Automi a pila
6.1 Definizione di automi a pila
6.2 I linguaggi di un PDA
6.3 Equivalenza di PDA e CFG
6.4 Automi a pila deterministici
6.5 Riepilogo
6.6 Bibliografia

7 Proprieta' dei linguaggi liberi dal contesto
7.1 Forme normali per grammatiche libere dal contesto
7.2 Il pumping lemma per i linguaggi liberi dal contesto
7.3 Proprieta' di chiusura dei linguaggi liberi dal contesto
7.4 Proprieta' di decisione dei CFL
7.5 Riepilogo
7.6 Bibliografia

8 Macchine di Turing: introduzione
8.1 Problemi che i calcolatori non possono risolvere
8.2 La macchina di Turing
8.3 Tecniche di programmazione per le macchine di Turing
8.4 Estensioni alla macchina di Turing semplice
8.5 Macchine di Turing ridotte
8.6 Le macchine di Turing e i computer
8.7 Riepilogo
8.8 Bibliografia

9 Indecidibilita'
9.1 Un linguaggio non ricorsivamente enumerabile
9.2 Un problema indecidibile ma ricorsivamente enumerabile
9.3 Problemi indecidibili relativi alle macchine di Turing
9.4 Il problema di corrispondenza di Post
9.5 Altri problemi indecidibili
9.6 Riepilogo
9.7 Bibliografia

10 Problemi intrattabili
10.1 Le classi P ed NP
10.2 Un problema NP-completo
10.3 Un problema di soddisfacibilita' vincolato
10.4 Altri problemi NP-completi
10.5 Riepilogo
10.6 Bibliografia

11 Altre classi di problemi
11.1 Complementi dei linguaggi in NP
11.2 Problemi risolvibili in spazio polinomiale
11.3 Un problema completo per PS
11.4 Classi di linguaggi basate sulla randomizzazione
11.5 Complessita' e numeri primi
11.6 Riepilogo
11.7 Bibliografia

Indice analitico