Università Roma Tre

Proprietà elementari dei linguaggi: operazioni su linguaggi, operatore di Kleene, espressioni regolari, cardinalità dei linguaggi
Grammatiche formali: grammatiche di Chomsky, produzioni, generazione e riconoscimento di linguaggi.
Linguaggi regolari: automi a stati finiti, relazioni tra automi e linguaggi regolari, pumping lemma, chiusura dei linguaggi regolari, espressioni regolari e linguaggi regolari, decidibilità e linguaggi regolari, teorema di Myhill-Nerode.

G. Ausiello, F. d'Amore, G. Gambosi, "Linguaggi Modelli Complessità", FrancoAngeli

Linguaggi non contestuali.
Cardinalità di insiemi infiniti.
Macchine di Turing (MT) e Turing calcolabilità: funzionamento delle MT, MT multinastro, MT non deterministiche, descrizione linearizzata delle MT, MT universale, il problema della fermata, calcolabilità secondo Turing, teorema di Rice, linguaggi di tipo 0 e MT.
Macchine a registri (RAM): modelli di costo per RAM, modello a costi uniformi, modello a costi logaritimici, RAM e MT.
Teoria della complessità: tipologie di problemi, problemi di decisione, complessità e problemi di decisione su linguaggi, classi di complessità, relazioni elementari tra classi di complessità, riducibilità, completezza, la classe NP, NP-completezza, esempi di problemi NP-completi, la classe Pspazio, Pspazio-completezza, teorema di Savitch, le classi L e NL, NL-completezza.

Michael Sipser, "Introduction to the Theory of Computation", Second Edition, Thompson.