Basi Teoriche dell'Informatica 2009/10

 

Lezioni

1. Venerdì 12 marzo 2010
Introduzione al corso. Nozione di alfabeto. Stringhe e loro proprietà. Nozione di linguaggio, operazioni sui linguaggi, omomorfismi fra linguaggi.   

2. Venerdì 19 marzo 2010
Rappresentazione dei linguaggi. Grammatiche, forme proposizionali e derivazioni. Classificazione delle grammatiche.   

3. Venerdì 9 aprile 2010
Linguaggi regolari ed espressioni regolari. Riconoscitori. Classificazione dei riconoscitori. Automi a stati finiti deterministici.   

4. Venerdì 16 aprile 2010
Automi a stati finiti non deterministici. Esempi.  

5. Venerdì 23 aprile 2010
Equivalenza tra automi finiti deterministici e non deterministici in termini di capacità riconoscitiva. Esempi.  

6. Venerdì 30 aprile 2010
Automi finiti non deterministici con epsilon-transizioni. Esempi. Proprietà di chiusura degli insiemi AF-regolari (unione, concatenazione, chiusura di Kleene). Equivalenza fra linguaggi regolari e AF-regolari.  

7. Venerdì 7 maggio 2010
Equivalenza fra automi finiti ed espressioni regolari in termini di capacità riconoscitiva/descrittiva ed esempi. Grammatiche regolari. Equivalenza fra grammatiche regolari e automi finiti in termini di capacità riconoscitiva/generativa.  

8. Venerdì 14 maggio 2010
Pumping lemma, applicazioni ed esempi.  

9. Venerdì 21 maggio 2010
Grammatiche context free, derivazioni sinistre e destre, alberi di derivazione.  

10. Venerdì 28 maggio 2010
Semplificazione delle grammatiche context free. Eliminazione dei simboli inutili, delle produzioni unitarie, delle epsilon produzioni.   

11. Venerdì 4 giugno 2010
Forma Normale di Chomsky. Grammatiche ambigue ed inerentemente ambigue.   

12. Venerdì 11 giugno 2010
Macchina di Turing. Linguaggi ricorsivamente enumerabili. Esempi.   

13. Venerdì 18 giugno 2010
Esercitazione.   

Home
Corso di Progetto Software 2007/2008
Corso di Progetto Software 2008/2009

Corso di Logica Computazionale 2008/2009
Corso di Logica Computazionale 2009/2010
Corso di Logica Computazionale 2010/2011
Corso di Logica Computazionale 2011/2012
Corso di Logica Computazionale 2012/2013
Corso di Logica Computazionale 2013/2014
Corso di Basi Teoriche dell'Informatica 2009/2010