Fondamenti Dell'informatica 2011/2012

Introduzione alla teoria della computazione. Linguaggi regolari. Definizione di linguaggio formale e notazioni. Automa a  stati finiti deterministico. Automa a stati finiti non deterministico. Teorema di equivalenza di automa non  deterministico con automa deterministico. Espressioni regolari. PumpingLemma. Proprieta' di chiusura. Algoritmi per  automi a stati finiti. Minimizzazione di automi. Linguaggi context-free. Grammatiche contextfree. Derivazioni. Automi a  pila. Teorema di equivalenza grammatiche context-free / automi a pila. Proprieta' di chiusura. Linguaggi non contextfree. Determinismo. Definizione macchina di Turing. Computazioni di macchine diTuring. Estensioni di macchine di  Turing. Linguaggi ricorsivamente enumerabili e linguaggi ricorsivi. La tesi di Turing-Church. Il linguaggio diagonale.  Macchine di Turing Universali. Il problema della fermata. Problemi indecidibili.