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