Programma tentativo

• Introduzione al corso: algoritmi, problemi, modelli di calcolo
• Caratteristiche elementari dei linguaggi
• Grammatiche di Chomsky e loro gerarchia
• Generazione ed accettazione di linguaggi
• Riconoscimento di linguaggi: automi, configurazioni, computazioni
• Automi a stati finiti deterministici e non deterministici; equivalenza tra essi
• Grammatiche di tipo 3 e loro equivalenza con gli ASF
• Espressioni regolari e loro equivalenza con ASF e grammatiche regolari
• Pumping lemma per i linguaggi regolari
• Proprietà di chiusura dei linguaggi regolari
• Predicati decidibili sui linguaggi regolari

• Automi a stati finiti minimi e minimizzazione di ASF

• Linguaggi context free
• Grammatiche di tipo 2: forme ridotte e forme normali (Chomsky, Greibach)
• Proprietà di chiusura dei linguaggi CF
• Decidibilità di predicati su linguaggi CF
• Pumping lemma per i linguaggi context free
• Automi a pila e linguaggi context free
• Automi a pila deterministici