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.

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.

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