Università Roma Tre

- Proprietà elementari dei linguaggi: operazioni su linguaggi, operatore di Kleene, espressioni regolari, cardinalità dei linguaggi.
- Grammatiche formali: grammatiche di Chomsky, produzioni, 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.
- Linguaggi non contestuali.

- Slide fornite dal docente.
- Libri consigliati:
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente).
M. Sipser, Introduction to the Theory of Computation, Thompson.

- 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.

- Slide fornite dal docente.
- Libri consigliati:
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente).
M. Sipser, Introduction to the Theory of Computation, Thompson.