Abschnittsübersicht

  • 1) 26 febbraio: introduzione al corso; alfabeti, stringhe, linguaggi

    2) 27 febbario: automi deterministici (DFA)

    3) 5 marzo: automi non deterministici (NFA), trasformazione da DFA in NFA

    4) 6 marzo: epsilon-NFA, trasformazione da epsilon-NFA in NFA

    5) 12 marzo:   minimizzazione di DFA, espressioni regolari

    6) 13 marzo: trasformazione da espressioni regolari in epsilon-NFA, proprietà dei regolari, pumping lemma  per i regolari

    7) 19 marzo: prova del pumping lemma, esempi, esercizi

    8) 20 marzo: ripasso grammatiche context-free, automi a pila (PDA), esempi

    9) 26 marzo: automi a pila deterministici (DPDA), provare che una grammatica genera un dato linguaggio

    10) 27 marzo: equivalenza tra grammatiche context-free e PDA, pumping lemma per i context-free

    11) 2 aprile: pumping lemma per i context-free, proprietà di chiusura dei context-free

    12) 3 aprile [Dagnino]: esercizi guidati sulla prima parte

    13) 9 aprile:  macchine di Turing (MdT) come riconoscitori

    14) 10 aprile: linguaggi ricorsivi e ricorsivamente numerabili (r.e.), MdT come "calcolatori"

    15) 16 aprile:  funzioni primitive ricorsive (PR), esempi di riduzione

    16) 30 aprile: esempi PR, numerazione effettiva, PR non Turing-completo

    17) 7 maggio: tesi di Church-Turing, halting problem

    18) 8 maggio: macchina universale, insiemi ricorsivi e r.e., teorema di Post, proprietà di chiusura di ricorsivi e r.e.

    19) 14 maggio: problemi decidibili e semidecidibili, riduzione, esempi, proprietà della riduzione

    20) 15 maggio: esercizi su riduzione

    21) 21 maggio: caratterizzazione insiemi r.e., tecnica a zig-zag

    22) 22 maggio: insieme delle funzioni totali non ricorsivamente numerabile, teorema di Rice, esempi di applicazione

    23) 28 maggio: prova del teorema di Rice, esercizi

    24) 29 maggio: [Dagnino]: esercizi guidati sulla seconda parte